/*-------------------------------------------------------------------------
 *
 * tuplesort.c
 *	  一般化的元组排序例程。
 *
 * 本模块处理堆元组、索引元组或单个数据项的排序（并且可以轻松支持其他类型的可排序对象，如有必要）。它在处理小量和大量数据时都能高效运行。小量数据使用qsort()在内存中进行排序；大规模数据使用临时文件和标准外部排序算法进行排序。
 *
 * 有关外部排序算法的详细信息，请参阅Knuth，第3卷。我们使用的算法是平衡的k路归并。在PostgreSQL 15之前，我们使用的是多相归并算法（Knuth的算法5.4.2D），但使用现代硬件时，直观的平衡归并效果更好。Knuth假设磁带驱动器是昂贵的，并且尤其认为运行的数量总是比磁带驱动器多。多相归并算法在保持所有磁带驱动器忙碌方面表现良好，但在我们的实现中，“磁带驱动器”的成本不比几个Kb的内存缓冲区更高，因此我们可以拥有许多这样的设备。特别地，如果我们能够拥有与已排序运行数量相同的磁带驱动器，则可以消除任何重复的I/O。
 *
 * 从历史上看，我们使用替换选择将输入划分为已排序的运行，以堆的形式实现优先级树（基本上是Knuth的算法5.2.3H），但我们现在总是使用快速排序生成运行。
 *
 * 每个排序操作允许的大致内存量由调用者以千字节为单位指定（大多数通过work_mem传递）。最初，我们会吸收元组，并简单地将它们存储在一个未排序的数组中，只要我们没有超过workMem。如果在不超过workMem的情况下到达输入末尾，我们将使用qsort()对数组进行排序，并随后通过顺序扫描元组数组返回元组。如果我们超过了workMem，我们开始将元组发出到临时磁带中的已排序运行。当在快速排序后批量转储元组时，我们开始用一个新输出磁带开一个新运行。如果达到最大磁带数量，我们以循环的方式在现有磁带上写入后续运行。在这种情况下，我们将需要多次归并才能完成合并。在达到输入末尾后，我们将内存中剩余的元组转储到最终运行中，然后合并这些运行。
 *
 * 在合并运行时，我们使用一个堆，仅包含每个来源运行的最前面的元组；我们反复输出最小的元组，并用其来源磁带的下一个元组（如有）替换它。当堆为空时，合并完成。因此，基本合并算法仅需极少的内存——对于M路合并，只需要M个元组，而M限制为一个小数字。然而，我们仍然可以通过从每个源磁带预读取额外的块，充分利用我们的完整workMem分配。没有预读取的情况下，我们对临时文件的访问模式将非常不规律；平均而言，我们将在写入M个块到输出磁带的同时从每个M个源磁带读取一个块，因此没有任何顺序访问，导致大多数Unix内核使用的预读方法失效。更糟的是，输出磁带将以非常随机的顺序写入临时文件的块，确保在读取该磁带时会更加糟糕。因此，简单的合并遍历最终会导致很多等待磁盘寻址。我们可以通过顺序地从每个源磁带预读取来改善这个问题，依次加载约workMem/M字节，并立即使这些顺序块可供重用。这种方法有助于将读取和写入访问本地化。预读取由logtape.c处理，我们只需告诉它为缓冲区使用多少内存。
 *
 * 在当前代码中，我们根据workMem确定输入磁带的数量M：我们希望workMem/M足够大，以便我们在每次从磁带读取时都读取相当数量的数据，以保持上述描述的访问局部性。然而，具有大workMem的情况下，我们可以有很多磁带。逻辑“磁带”由logtape.c实现，该模块在每个块从其“磁带”读取后立即回收磁盘空间以避免空间浪费。
 *
 * 当调用者请求对排序结果的随机访问时，我们在一个逻辑磁带上形成最终已排序的运行，然后“冻结”它，以便我们可以随机访问。当调用者不需要随机访问时，我们在每个逻辑磁带减少到一次运行时，就从tuplesort_performsort()返回。然后在调用者重复调用tuplesort_getXXX时，在线执行最终合并；这节省了将所有数据写入磁盘然后再读取的一个循环。
 *
 * 本模块支持并行排序。并行排序涉及一个或多个工作进程与一个领导进程之间的协调，每个进程都有自己的tuplesort状态。领导进程（更准确地说，与领导进程相关联的Tuplesortstate）创建一个完整的磁带集，包含一运行以归并的工作磁带；每个工作进程都有一个运行。然后进行归并。工作进程被保证从其部分输入中产生恰好一个输出运行。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/utils/sort/tuplesort.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include <limits.h>

#include "access/hash.h"
#include "access/htup_details.h"
#include "access/nbtree.h"
#include "catalog/index.h"
#include "catalog/pg_am.h"
#include "commands/tablespace.h"
#include "executor/executor.h"
#include "miscadmin.h"
#include "pg_trace.h"
#include "utils/datum.h"
#include "utils/logtape.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
#include "utils/pg_rusage.h"
#include "utils/rel.h"
#include "utils/sortsupport.h"
#include "utils/tuplesort.h"


/* sort-type codes for sort__start probes */
#define HEAP_SORT		0
#define INDEX_SORT		1
#define DATUM_SORT		2
#define CLUSTER_SORT	3

/* 从状态加载并行代码以进行sort__start探测 */
#define PARALLEL_SORT(state)	((state)->shared == NULL ? 0 : \
								 (state)->worker >= 0 ? 1 : 2)

/*
 * memtuples数组的初始大小。我们试图选择这个大小以确保
 * 数组不超过ALLOCSET_SEPARATE_THRESHOLD，并且分配的开销
 * 可能降低。然而，我们不考虑小于1024的数组大小。
 *
 */
#define INITIAL_MEMTUPSIZE Max(1024, \
	ALLOCSET_SEPARATE_THRESHOLD / sizeof(SortTuple) + 1)

/* GUC 变量 */
#ifdef TRACE_SORT
bool		trace_sort = false;
#endif

#ifdef DEBUG_BOUNDED_SORT
bool		optimize_bounded_sort = true;
#endif


/*
 * 我们实际排序的对象是SortTuple结构。这些结构包含
 * 对元组本身的指针（可能是MinimalTuple或IndexTuple），
 * 这是一个单独的palloc块---我们假设它只是一个块并且
 * 可以通过简单的pfree()释放（在合并期间除外，当时我们使用一个
 * 简单的slab分配器）。SortTuple还包含元组的第一关键
 * 列以Datum/nullflag格式表示，以及一个源/输入带号，
 * 用于跟踪每个堆元素/槽在合并期间属于哪个磁带。
 *
 * 存储第一关键列使我们能够在元组比较期间节省heap_getattr或
 * index_getattr调用。我们可以提取并保存所有关键列，而不仅仅是
 * 第一个，但这会增加代码复杂性和开销，并且在第一关键决定
 * 比较结果的常见情况下并不会节省任何比较周期。请注意，对于
 * 通过引用传递的数据类型，datum1指向“元组”存储。
 *
 * 有一种特殊情况：当排序支持基础设施提供“缩略关键”
 * 表示时，关键（通常）是通过值传递的代理以供通过引用
 * 类型使用。在这种情况下，缩略关键存储在datum1中，以替代
 * 实际的第一关键列。
 *
 * 在排序单个Datum时，数据值由datum1/isnull1直接表示，
 * 用于通过值传递的类型（或空值）。如果数据类型是通过
 * 引用传递并且isnull1为false，则“元组”指向一个单独
 * palloc的数据值，否则“元组”为NULL。此时，datum1的值为
 * “元组”的相同指针，或者是上面描述的缩略关键值。
 * 因此，在通过引用案例中，始终优先使用“元组”作为
 * 权威值，而不是datum1。
 */
typedef struct
{
	void	   *tuple;			/* 元组本身 */
	Datum		datum1;			/* 第一关键列的值 */
	bool		isnull1;		/* 第一关键列是否为NULL？ */
	int			srctape;		/* 源磁带号 */
} SortTuple;

/*
 * 在合并期间，我们使用预分配的固定大小槽来保存
 * 元组。为了避免palloc/pfree的开销。
 *
 * 合并不需要大量内存，因此我们可以通过使用过度大小的
 * 槽来浪费一些。 如果元组大于1 kB，则palloc()的开销
 * 不再显著。
 *
 * 'nextfree' 在这个块处于空闲列表时有效。当在使用时，
 * 槽中保存一个元组。
 */
#define SLAB_SLOT_SIZE 1024

typedef union SlabSlot
{
	union SlabSlot *nextfree;
	char		buffer[SLAB_SLOT_SIZE];
} SlabSlot;

/*
 * Tuplesort对象的可能状态。这些状态在Tuplesort例程调用
 * 之间持续存在。
 */
typedef enum
{
	TSS_INITIAL,				/* 正在加载元组；仍在内存限制内 */
	TSS_BOUNDED,				/* 加载元组到限大小堆 */
	TSS_BUILDRUNS,				/* 加载元组；写入磁带 */
	TSS_SORTEDINMEM,			/* 排序完全在内存中完成 */
	TSS_SORTEDONTAPE,			/* 排序完成，最终运行在磁带上 */
	TSS_FINALMERGE				/* 进行即时最终合并 */
} TupSortStatus;

/*
 * 计算需要使用的磁带数量的参数 --- 见 inittapes()
 * 和 tuplesort_merge_order()。
 *
 * 在这个计算中，我们假设每个磁带将花费我们大约 1 个块
 * 的缓冲区空间。这忽略了每个磁带所需的所有其他数据
 * 结构的开销，但可能足够接近。
 *
 * MERGE_BUFFER_SIZE 是我们希望为每个
 * 输入磁带分配的缓冲区空间，用于预读取（见文件顶部的讨论）。
 * 这*是额外的*，加上已经包括在 TAPE_BUFFER_OVERHEAD 中的 1 个块。
 */
#define MINORDER		6		/* 最小合并顺序 */
#define MAXORDER		500		/* 最大合并顺序 */
#define TAPE_BUFFER_OVERHEAD		BLCKSZ
#define MERGE_BUFFER_SIZE			(BLCKSZ * 32)

typedef int (*SortTupleComparator) (const SortTuple *a, const SortTuple *b,
									Tuplesortstate *state);

/*
 * Tuplesort 操作的私有状态。
 */
struct Tuplesortstate
{
	TupSortStatus status;		/* 上述显示的枚举值 */
	int			nKeys;			/* 排序键中的列数 */
	int			sortopt;		/* 用于设置排序的标志位掩码 */
	bool		bounded;		/* 调用者是否指定了最大返回元组数？ */
	bool		boundUsed;		/* 如果我们使用了限大小堆则为真 */
	int			bound;			/* 如果是限大小，最大元组数 */
	bool		tuples;			/* SortTuple.tuple 能否被设置？ */
	int64		availMem;		/* 剩余可用内存，字节数 */
	int64		allowedMem;		/* 允许的总内存，字节数 */
	int			maxTapes;		/* 每次合并的最大输入磁带数量 */
	int64		maxSpace;		/* 排序的组占用的最大空间，无论是内存中还是磁盘上 */
	bool		isMaxSpaceDisk; /* 当 maxSpace 为磁盘空间的值时为真，
	     当它为内存空间的值时为假 */
	TupSortStatus maxSpaceStatus;	/* 达到 maxSpace 时的排序状态 */
	MemoryContext maincontext;	/* 跨多个批次持久化的元组排序元数据的内存上下文 */
	MemoryContext sortcontext;	/* 持有大部分排序数据的内存上下文 */
	MemoryContext tuplecontext; /* 元组数据的排序上下文的子上下文 */
	LogicalTapeSet *tapeset;	/* 临时文件中磁带的 logtape.c 对象 */

	/*
	 * 这些函数指针将必须知道我们正在排序的元组类型
	 * 的例程与不需要知道的例程解耦。
	 * 它们由 tuplesort_begin_xxx 例程设置。
	 *
	 * 比较两个元组的函数；结果符合 qsort() 约定，即：
	 * <0，0，>0 根据 a<b，a=b，a>b。API 必须匹配
	 * qsort_arg_comparator。
	 */
	SortTupleComparator comparetup;

	/*
	 * 将提供的输入元组复制到 palloc'd 空间并设置
	 * 其 SortTuple 表示（即，设置 tuple/datum1/isnull1）。此外，
	 * state->availMem 必须减少用于元组复制的空间量
	 * （注意 SortTuple 结构本身不计算在内）。
	 */
	void		(*copytup) (Tuplesortstate *state, SortTuple *stup, void *tup);

	/*
	 * 函数用于将存储的元组写入磁带。元组在磁带上的表示不必与内存中的表示相同；关于磁带表示的要求如下所示。除非使用了 slab 分配器，否则在写入元组后，pfree() 异常数据（而不是 SortTuple 结构！），并将 state->availMem 增加释放的内存空间。
	 */
	void		(*writetup) (Tuplesortstate *state, LogicalTape *tape,
							 SortTuple *stup);

	/*
	 * 函数用于从磁带读取存储的元组回到内存中。“len”是已读取的存储元组的长度。元组是从 slab 内存区域分配的，或者是通过 palloc() 分配的，见 readtup_alloc()。
	 */
	void		(*readtup) (Tuplesortstate *state, SortTuple *stup,
							LogicalTape *tape, unsigned int len);

	/*
	 * SortTuple 的 datum1 和 isnull1 成员是否由上述例程维护。如果不是，则一些排序特化将被禁用。
	 */
	bool		haveDatum1;

	/*
	 * 这个数组保存当前在排序内存中的元组。如果我们处于 INITIAL 状态，元组没有特定的顺序；如果我们处于 SORTEDINMEM 状态，元组是最终的排序顺序；在 BUILDRUNS 和 FINALMERGE 状态中，元组按算法 H 的“堆”顺序组织。在 SORTEDONTAPE 状态中，不使用该数组。
	 */
	SortTuple  *memtuples;		/* SortTuple 结构的数组 */
	int			memtupcount;	/* 当前存在的元组数量 */
	int			memtupsize;		/* memtuples 数组的分配长度 */
	bool		growmemtuples;	/* memtuples 的增长尚在进行中？ */

	/*
	 * 元组的内存有时使用简单的 slab 分配器分配，而不是使用 palloc()。目前，当我们开始合并时会切换到 slab 分配。合并只需要在任何时候保持少量固定数量的元组在内存中，因此我们可以通过回收固定数量的固定大小的槽来避免 palloc/pfree 的开销。
	 *
	 * 对于 slab，我们使用一个大的分配，将其划分为 SLAB_SLOT_SIZE 个槽。该分配的大小为每个磁带一个槽，再加一个额外的槽。我们需要这么多槽来保持在合并期间保存在堆中的所有元组，加上我们最后从排序中返回的一个元组，使用 tuplesort_gettuple。
	 *
	 * 最初，所有槽都保存在自由槽的链表中。当从磁带读取元组时，如果适合，则放置到下一个可用槽中。如果元组大于 SLAB_SLOT_SIZE，则改为通过 palloc() 分配。
	 *
	 * 当处理完一个元组后，我们将槽返回到自由列表，或在它是通过 palloc() 分配的情况下调用 pfree()。如果其指针值在 slabMemoryBegin 和 -End 之间，我们知道该元组是从 slab 中分配的。
	 *
	 * 当使用 slab 分配器时，跟踪内存使用的 USEMEM/LACKMEM 机制不再使用。
	 */
	bool		slabAllocatorUsed;

	char	   *slabMemoryBegin;	/* slab 内存区域的开始 */
	char	   *slabMemoryEnd;	/* slab 内存区域的结束 */
	SlabSlot   *slabFreeHead;	/* 自由列表的头部 */

	/* 用于输入和输出磁带缓冲区的内存。 */
	size_t		tape_buffer_mem;

	/*
	 * 当我们在tuplesort_gettuple_XXX中将元组返回给调用者时，
	 * 如果它来自磁带（即在TSS_SORTEDONTAPE或TSS_FINALMERGE
	 * 模式下），我们会记住元组在'lastReturnedTuple'中，以便
	 * 在下一个gettuple调用时可以回收内存。
	 */
	void	   *lastReturnedTuple;

	/*
	 * 在构建初始运行时，这是当前的输出运行编号。
	 * 之后，它是我们制作的初始运行的数量。
	 */
	int			currentRun;

	/*
	 * 逻辑磁带，用于合并。
	 *
	 * 初始运行被写入输出磁带。在每次合并传递中，
	 * 上一次传递的输出磁带成为输入磁带，必要时创建新的
	 * 输出磁带。当nInputTapes等于
	 * nInputRuns时，只剩下一个合并传递。
	 */
	LogicalTape **inputTapes;
	int			nInputTapes;
	int			nInputRuns;

	LogicalTape **outputTapes;
	int			nOutputTapes;
	int			nOutputRuns;

	LogicalTape *destTape;		/* 当前输出磁带 */

	/*
	 * 这些变量在排序完成后用于跟踪下一个要返回的元组。
	 * （在磁带的情况下，磁带的当前读取位置
	 * 也是关键状态。）
	 */
	LogicalTape *result_tape;	/* 实际完成输出的磁带 */
	int			current;		/* 数组索引（仅在SORTEDINMEM时使用） */
	bool		eof_reached;	/* 到达EOF（需要用于游标） */

	/* markpos_xxx保存用于标记和恢复的标记位置 */
	long		markpos_block;	/* 磁带块#（仅在SORTEDONTAPE时使用） */
	int			markpos_offset; /* 保存的"当前"，或磁带块中的偏移量 */
	bool		markpos_eof;	/* 保存的"eof_reached" */

	/*
	 * 这些变量在并行排序过程中使用。
	 *
	 * worker是我们的工作标识符。遵循一般约定，
	 * -1值与领导者元组排序相关，值>= 0则与
	 * 工作元组排序相关。(-1也可以是串行元组排序。)
	 *
	 * shared是可变的共享内存状态，用于协调
	 * 并行排序。
	 *
	 * nParticipants是领导者已知的实际启动的工作
	 * Tuplesortstates的数量，这意味着它们必须
	 * 完成领导者需要合并的运行。通常包括
	 * 由领导进程本身持有的工作状态。仅在
	 * 领导Tuplesortstate中设置。
	 */
	int			worker;
	Sharedsort *shared;
	int			nParticipants;

	/*
	 * sortKeys变量用于除哈希索引
	 * 情况之外的所有情况；它由tuplesort_begin_xxx设置。
	 * tupDesc仅被MinimalTuple和CLUSTER例程使用。
	 */
	TupleDesc	tupDesc;
	SortSupport sortKeys;		/* 长度为nKeys的数组 */

	/*
	 * 该变量由单键MinimalTuple案例和
	 * Datum案例共享（两者都使用qsort_ssup()）。
	 * 否则，它为空。该字段中值的存在也被
	 * 各种排序专门化函数检查，作为在
	 * 平局情况下比较领先键以确定是否有任何后续
	 * 键要排序的优化。
	 */
	SortSupport onlyKey;

	/*
	 * 管理"缩略键"排序支持例程的附加状态
	 * （目前可能被除哈希索引情况之外的所有情况使用）。
	 * 跟踪优化效果测试的间隔。
	 */
	int64		abbrevNext;		/* 检查下一个适用性的元组# */

	/*
	 * 这些变量是特定于 CLUSTER 案例的；它们由
	 * tuplesort_begin_cluster 设置。
	 */
	IndexInfo  *indexInfo;		/* 关于用于参考的索引的信息 */
	EState	   *estate;			/* 用于评估索引表达式 */

	/*
	 * 这些变量是特定于 IndexTuple 案例的；它们由
	 * tuplesort_begin_index_xxx 设置，仅被 IndexTuple 例程使用。
	 */
	Relation	heapRel;		/* 正在构建索引的表 */
	Relation	indexRel;		/* 正在构建的索引 */

	/* 这些特定于 index_btree 子案例： */
	bool		enforceUnique;	/* 如果发现重复的元组则抱怨 */
	bool		uniqueNullsNotDistinct; /* 唯一约束的空值处理 */

	/* 这些特定于 index_hash 子案例： */
	uint32		high_mask;		/* 用于可排序部分的哈希代码掩码 */
	uint32		low_mask;
	uint32		max_buckets;

	/*
	 * 这些变量是特定于 Datum 案例的；它们由
	 * tuplesort_begin_datum 设置，仅被 DatumTuple 例程使用。
	 */
	Oid			datumType;
	/* 我们需要 typelen 来知道如何复制 Datums。 */
	int			datumTypeLen;

	/*
	 * 排序开始时的资源快照。
	 */
#ifdef TRACE_SORT
	PGRUsage	ru_start;
#endif
};

/*
 * tuplesort 并行操作的私有可变状态。 这分配在共享内存中。
 */
struct Sharedsort
{
	/* 互斥锁保护带之前的所有字段 */
	slock_t		mutex;

	/*
	 * currentWorker 为并行排序工作线程生成序数标识符。 这些从 0 开始，并且总是不间断的。
	 *
	 * 工作线程增加 workersFinished 以指示完成。如果这个
	 * 值等于领导者的 state.nParticipants，领导者准备合并工作线程运行。
	 */
	int			currentWorker;
	int			workersFinished;

	/* 临时文件空间 */
	SharedFileSet fileset;

	/* tapes 灵活数组的大小 */
	int			nTapes;

	/*
	 * 工作者用来报告领导者需要的信息，以将所有工作线程的带
	 * 连接成一个以便合并的带数组
	 */
	TapeShare	tapes[FLEXIBLE_ARRAY_MEMBER];
};

/*
 * 给定的元组是从 slab 内存区域分配的吗？
 */
#define IS_SLAB_SLOT(state, tuple) \
	((char *) (tuple) >= (state)->slabMemoryBegin && \
	 (char *) (tuple) < (state)->slabMemoryEnd)

/*
 * 将给定的元组返回到 slab 内存空闲列表，或者释放它
 * 如果它是 palloc'd。
 */
#define RELEASE_SLAB_SLOT(state, tuple) \
	do { \
		SlabSlot *fc_buf = (SlabSlot *) tuple; \
		\
		if (IS_SLAB_SLOT((state), fc_buf)) \
		{ \
			fc_buf->nextfree = (state)->slabFreeHead; \
			(state)->slabFreeHead = fc_buf; \
		} else \
			pfree(fc_buf); \
	} while(0)

#define COMPARETUP(state,a,b)	((*(state)->comparetup) (a, b, state))
#define COPYTUP(state,stup,tup) ((*(state)->copytup) (state, stup, tup))
#define WRITETUP(state,tape,stup)	((*(state)->writetup) (state, tape, stup))
#define READTUP(state,stup,tape,len) ((*(state)->readtup) (state, stup, tape, len))
#define LACKMEM(state)		((state)->availMem < 0 && !(state)->slabAllocatorUsed)
#define USEMEM(state,amt)	((state)->availMem -= (amt))
#define FREEMEM(state,amt)	((state)->availMem += (amt))
#define SERIAL(state)		((state)->shared == NULL)
#define WORKER(state)		((state)->shared && (state)->worker != -1)
#define LEADER(state)		((state)->shared && (state)->worker == -1)

/*
 * 关于元组的磁带表示的说明：
 *
 * 我们要求存储元组的第一个“unsigned int”为元组在磁带上的总大小，
 * 包括自身（所以它永远不为零；全零的unsigned int用于划分运行）。
 * 存储的元组的其余部分可能与内存中的元组表示相匹配，也可能不匹配 ---
 * 任何所需的转换都是writetup和readtup例程的工作。
 *
 * 如果state->sortopt包含TUPLESORT_RANDOMACCESS，则存储
 * 的元组表示后必须紧跟另一个“unsigned int”，它是长度的副本 ---
 * 所以总的磁带空间使用实际上比存储的长度值多
 * sizeof(unsigned int)。这允许向后读取。当未指定随机访问标志时，
 * 写入/读取例程可以省略额外的长度字。
 *
 * writetup预计将同时写入两个长度字以及元组数据。
 * 当调用readtup时，磁带的指针位于前长度字之后；
 * readtup必须读取元组数据并跳过后长度字（如果存在）。
 *
 * 写入/读取例程可以根据需要利用存储在Tuplesortstate记录中的
 * 元组描述数据。还预计它们会根据释放或消耗的内存空间
 * （不是磁带空间！）调整state->availMem。
 * writetup或readtup不会返回错误；它们在失败时应调用ereport()。
 *
 *
 * 关于内存消耗计算的说明：
 *
 * 我们将为元组分配的空间计入workMem限制，加上
 * variable-size memtuples数组所使用的空间。
 * 固定大小的空间不被计算；它小到无关紧要。
 *
 * 请注意，我们计算的是实际使用的空间（由GetMemoryChunkSpace
 * 显示）而不是最初请求的大小。这很重要，因为
 * palloc可能会增加相当大的开销。完全不是一个答案，因为
 * 我们不会计算palloc分配块中的任何浪费空间，但这
 * 好得多于7.3之前的做法。从9.6开始，调用者传递的元组
 * 使用单独的内存上下文。在某些关键增量时重设它显著改善了
 * 内存碎片问题。请注意，这使copytup例程有责任使用
 * 这些元组的正确内存上下文（并且不得将重置上下文用于
 * 需要跨越多个外部排序运行的任何事物）。readtup例程
 * 使用块分配器（它们不能使用重置上下文，因为在合并
 * 开始时会删除它）。
 */

/* 使用此宏时，注意len的双重评估 */
#define LogicalTapeReadExact(tape, ptr, len) \
	do { \
		if (LogicalTapeRead(tape, ptr, len) != (size_t) (len)) \
			elog(ERROR, "unexpected end of data"); \
	} while(0)


static Tuplesortstate *fc_tuplesort_begin_common(int fc_workMem,
											  SortCoordinate fc_coordinate,
											  int fc_sortopt);
static void fc_tuplesort_begin_batch(Tuplesortstate *fc_state);
static void fc_puttuple_common(Tuplesortstate *fc_state, SortTuple *fc_tuple);
static bool fc_consider_abort_common(Tuplesortstate *fc_state);
static void fc_inittapes(Tuplesortstate *fc_state, bool fc_mergeruns);
static void fc_inittapestate(Tuplesortstate *fc_state, int fc_maxTapes);
static void fc_selectnewtape(Tuplesortstate *fc_state);
static void fc_init_slab_allocator(Tuplesortstate *fc_state, int fc_numSlots);
static void fc_mergeruns(Tuplesortstate *fc_state);
static void fc_mergeonerun(Tuplesortstate *fc_state);
static void fc_beginmerge(Tuplesortstate *fc_state);
static bool fc_mergereadnext(Tuplesortstate *fc_state, LogicalTape *fc_srcTape, SortTuple *fc_stup);
static void fc_dumptuples(Tuplesortstate *fc_state, bool fc_alltuples);
static void fc_make_bounded_heap(Tuplesortstate *fc_state);
static void fc_sort_bounded_heap(Tuplesortstate *fc_state);
static void fc_tuplesort_sort_memtuples(Tuplesortstate *fc_state);
static void fc_tuplesort_heap_insert(Tuplesortstate *fc_state, SortTuple *fc_tuple);
static void fc_tuplesort_heap_replace_top(Tuplesortstate *fc_state, SortTuple *fc_tuple);
static void fc_tuplesort_heap_delete_top(Tuplesortstate *fc_state);
static void fc_reversedirection(Tuplesortstate *fc_state);
static unsigned int fc_getlen(LogicalTape *fc_tape, bool fc_eofOK);
static void fc_markrunend(LogicalTape *fc_tape);
static void *fc_readtup_alloc(Tuplesortstate *fc_state, Size fc_tuplen);
static int	fc_comparetup_heap(const SortTuple *fc_a, const SortTuple *fc_b,
							Tuplesortstate *fc_state);
static void fc_copytup_heap(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup);
static void fc_writetup_heap(Tuplesortstate *fc_state, LogicalTape *fc_tape,
						  SortTuple *fc_stup);
static void fc_readtup_heap(Tuplesortstate *fc_state, SortTuple *fc_stup,
						 LogicalTape *fc_tape, unsigned int fc_len);
static int	fc_comparetup_cluster(const SortTuple *fc_a, const SortTuple *fc_b,
							   Tuplesortstate *fc_state);
static void fc_copytup_cluster(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup);
static void fc_writetup_cluster(Tuplesortstate *fc_state, LogicalTape *fc_tape,
							 SortTuple *fc_stup);
static void fc_readtup_cluster(Tuplesortstate *fc_state, SortTuple *fc_stup,
							LogicalTape *fc_tape, unsigned int fc_len);
static int	fc_comparetup_index_btree(const SortTuple *fc_a, const SortTuple *fc_b,
								   Tuplesortstate *fc_state);
static int	fc_comparetup_index_hash(const SortTuple *fc_a, const SortTuple *fc_b,
								  Tuplesortstate *fc_state);
static void fc_copytup_index(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup);
static void fc_writetup_index(Tuplesortstate *fc_state, LogicalTape *fc_tape,
						   SortTuple *fc_stup);
static void fc_readtup_index(Tuplesortstate *fc_state, SortTuple *fc_stup,
						  LogicalTape *fc_tape, unsigned int fc_len);
static int	fc_comparetup_datum(const SortTuple *fc_a, const SortTuple *fc_b,
							 Tuplesortstate *fc_state);
static void fc_copytup_datum(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup);
static void fc_writetup_datum(Tuplesortstate *fc_state, LogicalTape *fc_tape,
						   SortTuple *fc_stup);
static void fc_readtup_datum(Tuplesortstate *fc_state, SortTuple *fc_stup,
						  LogicalTape *fc_tape, unsigned int fc_len);
static int	fc_worker_get_identifier(Tuplesortstate *fc_state);
static void fc_worker_freeze_result_tape(Tuplesortstate *fc_state);
static void fc_worker_nomergeruns(Tuplesortstate *fc_state);
static void fc_leader_takeover_tapes(Tuplesortstate *fc_state);
static void fc_free_sort_tuple(Tuplesortstate *fc_state, SortTuple *fc_stup);
static void fc_tuplesort_free(Tuplesortstate *fc_state);
static void fc_tuplesort_updatemax(Tuplesortstate *fc_state);

/*
 * 专门的比较器，可以嵌入到专门的排序中。目标是尝试在不需要跟踪比较器或元组指针的情况下对两个元组进行排序。
 *
 * XXX：目前，这些比较器会回退到比较函数，以第二次比较领先数据。
 *
 * XXX：目前，没有针对datum1是权威的情况进行专门化，我们甚至不需要回退到回调（对于像int4/int8/timestamp/date这样的类型是如此，但对于文本的缩写或多键排序则不然。可能会有！值得吗？
 */

/* 如果第一个键的比较器是ssup_datum_unsigned_compare，则使用 */
static pg_attribute_always_inline int fc_qsort_tuple_unsigned_compare(SortTuple *fc_a, SortTuple *fc_b, Tuplesortstate *fc_state)
{
	int			fc_compare;

	fc_compare = ApplyUnsignedSortComparator(fc_a->datum1, fc_a->isnull1,
										  fc_b->datum1, fc_b->isnull1,
										  &fc_state->sortKeys[0]);
	if (fc_compare != 0)
		return fc_compare;

	/*
	 * 当没有其他键可供排序时，调用平局打破函数没有必要浪费精力。
	 */
	if (fc_state->onlyKey != NULL)
		return 0;

	return fc_state->comparetup(fc_a, fc_b, fc_state);
}

#if SIZEOF_DATUM >= 8
/* 如果第一个键的比较器是ssup_datum_signed_compare，则使用 */
static pg_attribute_always_inline int fc_qsort_tuple_signed_compare(SortTuple *fc_a, SortTuple *fc_b, Tuplesortstate *fc_state)
{
	int			fc_compare;

	fc_compare = ApplySignedSortComparator(fc_a->datum1, fc_a->isnull1,
										fc_b->datum1, fc_b->isnull1,
										&fc_state->sortKeys[0]);

	if (fc_compare != 0)
		return fc_compare;

	/*
	 * 当没有其他键可供排序时，调用平局打破函数没有必要浪费精力。
	 */
	if (fc_state->onlyKey != NULL)
		return 0;

	return fc_state->comparetup(fc_a, fc_b, fc_state);
}
#endif

/* 如果第一个键的比较器是ssup_datum_int32_compare，则使用 */
static pg_attribute_always_inline int fc_qsort_tuple_int32_compare(SortTuple *fc_a, SortTuple *fc_b, Tuplesortstate *fc_state)
{
	int			fc_compare;

	fc_compare = ApplyInt32SortComparator(fc_a->datum1, fc_a->isnull1,
									   fc_b->datum1, fc_b->isnull1,
									   &fc_state->sortKeys[0]);

	if (fc_compare != 0)
		return fc_compare;

	/*
	 * 当没有其他键可供排序时，调用平局打破函数没有必要浪费精力。
	 */
	if (fc_state->onlyKey != NULL)
		return 0;

	return fc_state->comparetup(fc_a, fc_b, fc_state);
}

/*
 * 针对SortTuple对象的qsort特殊版本。qsort_tuple()可以对任何类型的SortTuples进行排序，使用适当的comparetup函数。
 * qsort_ssup()专门用于comparetup函数简化为ApplySortComparator()的情况，即单键MinimalTuple排序和Datum排序。
 * qsort_tuple_{unsigned,signed,int32}针对按值传递的领先数据的常见比较函数进行了专门化。
 */

#define ST_SORT qsort_tuple_unsigned
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE(a, b, state) fc_qsort_tuple_unsigned_compare(a, b, state)
#define ST_COMPARE_ARG_TYPE Tuplesortstate
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DEFINE
#include "lib/sort_template.h"

#if SIZEOF_DATUM >= 8
#define ST_SORT qsort_tuple_signed
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE(a, b, state) fc_qsort_tuple_signed_compare(a, b, state)
#define ST_COMPARE_ARG_TYPE Tuplesortstate
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DEFINE
#include "lib/sort_template.h"
#endif

#define ST_SORT qsort_tuple_int32
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE(a, b, state) fc_qsort_tuple_int32_compare(a, b, state)
#define ST_COMPARE_ARG_TYPE Tuplesortstate
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DEFINE
#include "lib/sort_template.h"

#define ST_SORT qsort_tuple
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE_RUNTIME_POINTER
#define ST_COMPARE_ARG_TYPE Tuplesortstate
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DECLARE
#define ST_DEFINE
#include "lib/sort_template.h"

#define ST_SORT qsort_ssup
#define ST_ELEMENT_TYPE SortTuple
#define ST_COMPARE(a, b, ssup) \
	ApplySortComparator((a)->datum1, (a)->isnull1, \
						(b)->datum1, (b)->isnull1, (ssup))
#define ST_COMPARE_ARG_TYPE SortSupportData
#define ST_CHECK_FOR_INTERRUPTS
#define ST_SCOPE static
#define ST_DEFINE
#include "lib/sort_template.h"

/*
 *		tuplesort_begin_xxx
 *
 * 为元组排序操作初始化。
 *
 * 在调用tuplesort_begin后，调用者应该调用tuplesort_putXXX零次或多次，然后在所有元组提供完毕后调用tuplesort_performsort。
 * 在performsort之后，通过调用tuplesort_getXXX以排序后的顺序检索元组，直到它返回false/NULL。（如果请求了随机访问，可以同时调用rescan、markpos和restorepos。）
 * 调用tuplesort_end以终止操作并释放内存/磁盘空间。
 *
 * 每个变体的tuplesort_begin都有一个workMem参数指定在将数据溢出到磁盘之前使用的最大千字节数的RAM。（该参数的正常值为work_mem，但某些调用者使用其他值。）每个变体还有一个sortopt，它是排序选项的位掩码。请参见tuplesort.h中的TUPLESORT_*定义。
 */

static Tuplesortstate *
fc_tuplesort_begin_common(int fc_workMem, SortCoordinate fc_coordinate, int fc_sortopt)
{
	Tuplesortstate *fc_state;
	MemoryContext fc_maincontext;
	MemoryContext fc_sortcontext;
	MemoryContext fc_oldcontext;

	/* 请参见leader_takeover_tapes()对随机访问支持的说明 */
	if (fc_coordinate && (fc_sortopt & TUPLESORT_RANDOMACCESS))
		elog(ERROR, "random access disallowed under parallel sort");

	/*
	 * 在tuplesort_reset中存活的内存上下文。此内存上下文保持在排序多个相似批次时有用的数据。
	 */
	fc_maincontext = AllocSetContextCreate(CurrentMemoryContext,
										"TupleSort main",
										ALLOCSET_DEFAULT_SIZES);

	/*
	 * 为一次排序操作创建一个工作内存上下文。此上下文的内容将在tuplesort_reset中删除。
	 */
	fc_sortcontext = AllocSetContextCreate(fc_maincontext,
										"TupleSort sort",
										ALLOCSET_DEFAULT_SIZES);

	/*
	 * 此外，为元组设置了一个工作内存上下文，在
	 * tuplesort_begin_batch 中。
	 */

	/*
	 * 在每个排序状态上下文中创建 Tuplesortstate。  这样，我们
	 * 在关闭时就不需要单独的 pfree() 操作。
	 */
	fc_oldcontext = MemoryContextSwitchTo(fc_maincontext);

	fc_state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));

#ifdef TRACE_SORT
	if (trace_sort)
		pg_rusage_init(&fc_state->ru_start);
#endif

	fc_state->sortopt = fc_sortopt;
	fc_state->tuples = true;

	/*
	 * workMem 被强制至少为 64KB，这是当前有效的
	 * work_mem GUC 的最小值。  这是为了防止并行排序调用者
	 * 以一种让每个工作者都留有非常少内存的方式分配内存。
	 */
	fc_state->allowedMem = Max(fc_workMem, 64) * (int64) 1024;
	fc_state->sortcontext = fc_sortcontext;
	fc_state->maincontext = fc_maincontext;

	/*
	 * 数组的初始大小必须超过 ALLOCSET_SEPARATE_THRESHOLD；
	 * 请参见 grow_memtuples() 中的注释。
	 */
	fc_state->memtupsize = INITIAL_MEMTUPSIZE;
	fc_state->memtuples = NULL;

	/*
	 * 在所有其他非并行相关状态之后，我们设置每个批次所需的
	 * 所有状态。
	 */
	fc_tuplesort_begin_batch(fc_state);

	/*
	 * 根据调用者提供的协调信息初始化与并行相关的状态
	 */
	if (!fc_coordinate)
	{
		/* 串行排序 */
		fc_state->shared = NULL;
		fc_state->worker = -1;
		fc_state->nParticipants = -1;
	}
	else if (fc_coordinate->isWorker)
	{
		/* 并行工作者从所有输入中产生一个最终运行 */
		fc_state->shared = fc_coordinate->sharedsort;
		fc_state->worker = fc_worker_get_identifier(fc_state);
		fc_state->nParticipants = -1;
	}
	else
	{
		/* 并行领导者状态仅用于最终合并 */
		fc_state->shared = fc_coordinate->sharedsort;
		fc_state->worker = -1;
		fc_state->nParticipants = fc_coordinate->nParticipants;
		Assert(fc_state->nParticipants >= 1);
	}

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

/*
 *		tuplesort_begin_batch
 *
 * 设置或重置处理此排序状态的新元组集所需的所有状态。
 * 同时由 tuplesort_begin_common（第一次使用此排序状态排序）
 * 和 tuplesort_reset（后续使用）调用。
 */
static void fc_tuplesort_begin_batch(Tuplesortstate *fc_state)
{
	MemoryContext fc_oldcontext;

	fc_oldcontext = MemoryContextSwitchTo(fc_state->maincontext);

	/*
	 * 调用元组（例如 IndexTuple）内存上下文。
	 *
	 * 专门用于调用者传递的元组的子上下文简化了内存管理。
	 * 在关键点重置可以减少碎片。 请注意，SortTuples 的
	 * memtuples 数组是在父上下文中分配的，而不是在此上下文中，
	 * 因为没有必要提前释放 memtuples。 对于有界排序，元组
	 * 可以按任何顺序被 pfreed，所以我们使用常规的 aset.c
	 * 上下文，以便可以利用释放的内存。 当排序没有界限时，
	 * 我们使用 generation.c 上下文，因为这使得分配更紧凑，
	 * 而且浪费更少。 分配的 CPU 效率也略高。
	 */
	if (fc_state->sortopt & TUPLESORT_ALLOWBOUNDED)
		fc_state->tuplecontext = AllocSetContextCreate(fc_state->sortcontext,
													"Caller tuples",
													ALLOCSET_DEFAULT_SIZES);
	else
		fc_state->tuplecontext = GenerationContextCreate(fc_state->sortcontext,
													  "Caller tuples",
													  ALLOCSET_DEFAULT_SIZES);


	fc_state->status = TSS_INITIAL;
	fc_state->bounded = false;
	fc_state->boundUsed = false;

	fc_state->availMem = fc_state->allowedMem;

	fc_state->tapeset = NULL;

	fc_state->memtupcount = 0;

	/*
	 * 数组的初始大小必须超过 ALLOCSET_SEPARATE_THRESHOLD；
	 * 请参见 grow_memtuples() 中的注释。
	 */
	fc_state->growmemtuples = true;
	fc_state->slabAllocatorUsed = false;
	if (fc_state->memtuples != NULL && fc_state->memtupsize != INITIAL_MEMTUPSIZE)
	{
		pfree(fc_state->memtuples);
		fc_state->memtuples = NULL;
		fc_state->memtupsize = INITIAL_MEMTUPSIZE;
	}
	if (fc_state->memtuples == NULL)
	{
		fc_state->memtuples = (SortTuple *) palloc(fc_state->memtupsize * sizeof(SortTuple));
		USEMEM(fc_state, GetMemoryChunkSpace(fc_state->memtuples));
	}

	/* workMem 必须足够大，以容纳最小的 memtuples 数组 */
	if (LACKMEM(fc_state))
		elog(ERROR, "insufficient memory allowed for sort");

	fc_state->currentRun = 0;

	/*
	 * 磁带变量（inputTapes、outputTapes 等）将由 inittapes()
	 * 初始化，如果需要的话。
	 */

	fc_state->result_tape = NULL;	/* 标记结果磁带尚未形成 */

	MemoryContextSwitchTo(fc_oldcontext);
}

Tuplesortstate * tuplesort_begin_heap(TupleDesc fc_tupDesc,
					 int fc_nkeys, AttrNumber *fc_attNums,
					 Oid *fc_sortOperators, Oid *fc_sortCollations,
					 bool *fc_nullsFirstFlags,
					 int fc_workMem, SortCoordinate fc_coordinate, int fc_sortopt)
{
	Tuplesortstate *fc_state = fc_tuplesort_begin_common(fc_workMem, fc_coordinate,
												   fc_sortopt);
	MemoryContext fc_oldcontext;
	int			fc_i;

	fc_oldcontext = MemoryContextSwitchTo(fc_state->maincontext);

	AssertArg(fc_nkeys > 0);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
			 fc_nkeys, fc_workMem, fc_sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif

	fc_state->nKeys = fc_nkeys;

	TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
								false,	/* 无唯一性检查 */
								nkeys,
								workMem,
								sortopt & TUPLESORT_RANDOMACCESS,
								PARALLEL_SORT(state));

	fc_state->comparetup = fc_comparetup_heap;
	fc_state->copytup = fc_copytup_heap;
	fc_state->writetup = fc_writetup_heap;
	fc_state->readtup = fc_readtup_heap;
	fc_state->haveDatum1 = true;

	fc_state->tupDesc = fc_tupDesc;	/* 假设我们不需要复制 tupDesc */
	fc_state->abbrevNext = 10;

	/* 为每一列准备 SortSupport 数据 */
	fc_state->sortKeys = (SortSupport) palloc0(fc_nkeys * sizeof(SortSupportData));

	for (fc_i = 0; fc_i < fc_nkeys; fc_i++)
	{
		SortSupport fc_sortKey = fc_state->sortKeys + fc_i;

		AssertArg(fc_attNums[fc_i] != 0);
		AssertArg(fc_sortOperators[fc_i] != 0);

		fc_sortKey->ssup_cxt = CurrentMemoryContext;
		fc_sortKey->ssup_collation = fc_sortCollations[fc_i];
		fc_sortKey->ssup_nulls_first = fc_nullsFirstFlags[fc_i];
		fc_sortKey->ssup_attno = fc_attNums[fc_i];
		/* 传达缩写优化原则上是否适用 */
		fc_sortKey->abbreviate = (fc_i == 0 && fc_state->haveDatum1);

		PrepareSortSupportFromOrderingOp(fc_sortOperators[fc_i], fc_sortKey);
	}

	/*
	 * "onlyKey" 优化不能与缩写键一起使用，因为
	 * 可能需要打破平局的比较。 通常，这种优化
	 * 对于按值传递的类型是有价值的，而缩写键通常
	 * 仅对按引用传递的类型有价值。
	 */
	if (fc_nkeys == 1 && !fc_state->sortKeys->abbrev_converter)
		fc_state->onlyKey = fc_state->sortKeys;

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

Tuplesortstate * tuplesort_begin_cluster(TupleDesc fc_tupDesc,
						Relation fc_indexRel,
						int fc_workMem,
						SortCoordinate fc_coordinate, int fc_sortopt)
{
	Tuplesortstate *fc_state = fc_tuplesort_begin_common(fc_workMem, fc_coordinate,
												   fc_sortopt);
	BTScanInsert fc_indexScanKey;
	MemoryContext fc_oldcontext;
	int			fc_i;

	Assert(fc_indexRel->rd_rel->relam == BTREE_AM_OID);

	fc_oldcontext = MemoryContextSwitchTo(fc_state->maincontext);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
			 RelationGetNumberOfAttributes(fc_indexRel),
			 fc_workMem, fc_sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif

	fc_state->nKeys = IndexRelationGetNumberOfKeyAttributes(fc_indexRel);

	TRACE_POSTGRESQL_SORT_START(CLUSTER_SORT,
								false,	/* 无唯一性检查 */
								state->nKeys,
								workMem,
								sortopt & TUPLESORT_RANDOMACCESS,
								PARALLEL_SORT(state));

	fc_state->comparetup = fc_comparetup_cluster;
	fc_state->copytup = fc_copytup_cluster;
	fc_state->writetup = fc_writetup_cluster;
	fc_state->readtup = fc_readtup_cluster;
	fc_state->abbrevNext = 10;

	fc_state->indexInfo = BuildIndexInfo(fc_indexRel);

	/*
	 * 如果我们没有简单的领先属性，我们目前不会初始化 datum1，因此禁用需要它的优化。
	 */
	if (fc_state->indexInfo->ii_IndexAttrNumbers[0] == 0)
		fc_state->haveDatum1 = false;
	else
		fc_state->haveDatum1 = true;

	fc_state->tupDesc = fc_tupDesc;	/* 假设我们不需要复制 tupDesc */

	fc_indexScanKey = _bt_mkscankey(fc_indexRel, NULL);

	if (fc_state->indexInfo->ii_Expressions != NULL)
	{
		TupleTableSlot *fc_slot;
		ExprContext *fc_econtext;

		/*
		 * 我们需要使用 FormIndexDatum 来评估索引表达式。为了做到这一点，我们需要一个 EState，以及一个 TupleTableSlot 来放置表元组。econtext 的 scantuple 也必须指向那个槽。
		 */
		fc_state->estate = CreateExecutorState();
		fc_slot = MakeSingleTupleTableSlot(fc_tupDesc, &TTSOpsHeapTuple);
		fc_econtext = GetPerTupleExprContext(fc_state->estate);
		fc_econtext->ecxt_scantuple = fc_slot;
	}

	/* 为每一列准备 SortSupport 数据 */
	fc_state->sortKeys = (SortSupport) palloc0(fc_state->nKeys *
											sizeof(SortSupportData));

	for (fc_i = 0; fc_i < fc_state->nKeys; fc_i++)
	{
		SortSupport fc_sortKey = fc_state->sortKeys + fc_i;
		ScanKey		fc_scanKey = fc_indexScanKey->scankeys + fc_i;
		int16		fc_strategy;

		fc_sortKey->ssup_cxt = CurrentMemoryContext;
		fc_sortKey->ssup_collation = fc_scanKey->sk_collation;
		fc_sortKey->ssup_nulls_first =
			(fc_scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
		fc_sortKey->ssup_attno = fc_scanKey->sk_attno;
		/* 传达缩写优化原则上是否适用 */
		fc_sortKey->abbreviate = (fc_i == 0 && fc_state->haveDatum1);

		AssertState(fc_sortKey->ssup_attno != 0);

		fc_strategy = (fc_scanKey->sk_flags & SK_BT_DESC) != 0 ?
			BTGreaterStrategyNumber : BTLessStrategyNumber;

		PrepareSortSupportFromIndexRel(fc_indexRel, fc_strategy, fc_sortKey);
	}

	pfree(fc_indexScanKey);

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

Tuplesortstate * tuplesort_begin_index_btree(Relation fc_heapRel,
							Relation fc_indexRel,
							bool fc_enforceUnique,
							bool fc_uniqueNullsNotDistinct,
							int fc_workMem,
							SortCoordinate fc_coordinate,
							int fc_sortopt)
{
	Tuplesortstate *fc_state = fc_tuplesort_begin_common(fc_workMem, fc_coordinate,
												   fc_sortopt);
	BTScanInsert fc_indexScanKey;
	MemoryContext fc_oldcontext;
	int			fc_i;

	fc_oldcontext = MemoryContextSwitchTo(fc_state->maincontext);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin index sort: unique = %c, workMem = %d, randomAccess = %c",
			 fc_enforceUnique ? 't' : 'f',
			 fc_workMem, fc_sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif

	fc_state->nKeys = IndexRelationGetNumberOfKeyAttributes(fc_indexRel);

	TRACE_POSTGRESQL_SORT_START(INDEX_SORT,
								enforceUnique,
								state->nKeys,
								workMem,
								sortopt & TUPLESORT_RANDOMACCESS,
								PARALLEL_SORT(state));

	fc_state->comparetup = fc_comparetup_index_btree;
	fc_state->copytup = fc_copytup_index;
	fc_state->writetup = fc_writetup_index;
	fc_state->readtup = fc_readtup_index;
	fc_state->abbrevNext = 10;
	fc_state->haveDatum1 = true;

	fc_state->heapRel = fc_heapRel;
	fc_state->indexRel = fc_indexRel;
	fc_state->enforceUnique = fc_enforceUnique;
	fc_state->uniqueNullsNotDistinct = fc_uniqueNullsNotDistinct;

	fc_indexScanKey = _bt_mkscankey(fc_indexRel, NULL);

	/* 为每一列准备 SortSupport 数据 */
	fc_state->sortKeys = (SortSupport) palloc0(fc_state->nKeys *
											sizeof(SortSupportData));

	for (fc_i = 0; fc_i < fc_state->nKeys; fc_i++)
	{
		SortSupport fc_sortKey = fc_state->sortKeys + fc_i;
		ScanKey		fc_scanKey = fc_indexScanKey->scankeys + fc_i;
		int16		fc_strategy;

		fc_sortKey->ssup_cxt = CurrentMemoryContext;
		fc_sortKey->ssup_collation = fc_scanKey->sk_collation;
		fc_sortKey->ssup_nulls_first =
			(fc_scanKey->sk_flags & SK_BT_NULLS_FIRST) != 0;
		fc_sortKey->ssup_attno = fc_scanKey->sk_attno;
		/* 传达缩写优化原则上是否适用 */
		fc_sortKey->abbreviate = (fc_i == 0 && fc_state->haveDatum1);

		AssertState(fc_sortKey->ssup_attno != 0);

		fc_strategy = (fc_scanKey->sk_flags & SK_BT_DESC) != 0 ?
			BTGreaterStrategyNumber : BTLessStrategyNumber;

		PrepareSortSupportFromIndexRel(fc_indexRel, fc_strategy, fc_sortKey);
	}

	pfree(fc_indexScanKey);

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

Tuplesortstate * tuplesort_begin_index_hash(Relation fc_heapRel,
						   Relation fc_indexRel,
						   uint32 fc_high_mask,
						   uint32 fc_low_mask,
						   uint32 fc_max_buckets,
						   int fc_workMem,
						   SortCoordinate fc_coordinate,
						   int fc_sortopt)
{
	Tuplesortstate *fc_state = fc_tuplesort_begin_common(fc_workMem, fc_coordinate,
												   fc_sortopt);
	MemoryContext fc_oldcontext;

	fc_oldcontext = MemoryContextSwitchTo(fc_state->maincontext);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin index sort: high_mask = 0x%x, low_mask = 0x%x, "
			 "max_buckets = 0x%x, workMem = %d, randomAccess = %c",
			 fc_high_mask,
			 fc_low_mask,
			 fc_max_buckets,
			 fc_workMem,
			 fc_sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif

	fc_state->nKeys = 1;			/* 只有一个排序列，即哈希码 */

	fc_state->comparetup = fc_comparetup_index_hash;
	fc_state->copytup = fc_copytup_index;
	fc_state->writetup = fc_writetup_index;
	fc_state->readtup = fc_readtup_index;
	fc_state->haveDatum1 = true;

	fc_state->heapRel = fc_heapRel;
	fc_state->indexRel = fc_indexRel;

	fc_state->high_mask = fc_high_mask;
	fc_state->low_mask = fc_low_mask;
	fc_state->max_buckets = fc_max_buckets;

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

Tuplesortstate * tuplesort_begin_index_gist(Relation fc_heapRel,
						   Relation fc_indexRel,
						   int fc_workMem,
						   SortCoordinate fc_coordinate,
						   int fc_sortopt)
{
	Tuplesortstate *fc_state = fc_tuplesort_begin_common(fc_workMem, fc_coordinate,
												   fc_sortopt);
	MemoryContext fc_oldcontext;
	int			fc_i;

	fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin index sort: workMem = %d, randomAccess = %c",
			 fc_workMem, fc_sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif

	fc_state->nKeys = IndexRelationGetNumberOfKeyAttributes(fc_indexRel);

	fc_state->comparetup = fc_comparetup_index_btree;
	fc_state->copytup = fc_copytup_index;
	fc_state->writetup = fc_writetup_index;
	fc_state->readtup = fc_readtup_index;
	fc_state->haveDatum1 = true;

	fc_state->heapRel = fc_heapRel;
	fc_state->indexRel = fc_indexRel;

	/* 为每一列准备 SortSupport 数据 */
	fc_state->sortKeys = (SortSupport) palloc0(fc_state->nKeys *
											sizeof(SortSupportData));

	for (fc_i = 0; fc_i < fc_state->nKeys; fc_i++)
	{
		SortSupport fc_sortKey = fc_state->sortKeys + fc_i;

		fc_sortKey->ssup_cxt = CurrentMemoryContext;
		fc_sortKey->ssup_collation = fc_indexRel->rd_indcollation[fc_i];
		fc_sortKey->ssup_nulls_first = false;
		fc_sortKey->ssup_attno = fc_i + 1;
		/* 传达缩写优化原则上是否适用 */
		fc_sortKey->abbreviate = (fc_i == 0 && fc_state->haveDatum1);

		AssertState(fc_sortKey->ssup_attno != 0);

		/* 查找排序支持函数 */
		PrepareSortSupportFromGistIndexRel(fc_indexRel, fc_sortKey);
	}

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

Tuplesortstate * tuplesort_begin_datum(Oid fc_datumType, Oid fc_sortOperator, Oid fc_sortCollation,
					  bool fc_nullsFirstFlag, int fc_workMem,
					  SortCoordinate fc_coordinate, int fc_sortopt)
{
	Tuplesortstate *fc_state = fc_tuplesort_begin_common(fc_workMem, fc_coordinate,
												   fc_sortopt);
	MemoryContext fc_oldcontext;
	int16		fc_typlen;
	bool		fc_typbyval;

	fc_oldcontext = MemoryContextSwitchTo(fc_state->maincontext);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin datum sort: workMem = %d, randomAccess = %c",
			 fc_workMem, fc_sortopt & TUPLESORT_RANDOMACCESS ? 't' : 'f');
#endif

	fc_state->nKeys = 1;			/* 始终是单列排序 */

	TRACE_POSTGRESQL_SORT_START(DATUM_SORT,
								false,	/* 无唯一性检查 */
								1,
								workMem,
								sortopt & TUPLESORT_RANDOMACCESS,
								PARALLEL_SORT(fc_state));

	fc_state->comparetup = fc_comparetup_datum;
	fc_state->copytup = fc_copytup_datum;
	fc_state->writetup = fc_writetup_datum;
	fc_state->readtup = fc_readtup_datum;
	fc_state->abbrevNext = 10;
	fc_state->haveDatum1 = true;

	fc_state->datumType = fc_datumType;

	/* 查找 datum 类型的必要属性 */
	get_typlenbyval(fc_datumType, &fc_typlen, &fc_typbyval);
	fc_state->datumTypeLen = fc_typlen;
	fc_state->tuples = !fc_typbyval;

	/* 准备 SortSupport 数据 */
	fc_state->sortKeys = (SortSupport) palloc0(sizeof(SortSupportData));

	fc_state->sortKeys->ssup_cxt = CurrentMemoryContext;
	fc_state->sortKeys->ssup_collation = fc_sortCollation;
	fc_state->sortKeys->ssup_nulls_first = fc_nullsFirstFlag;

	/*
	 * 这里的缩写仅对于引用类型可能。理论上，按值传递的数据类型可以有一种成本更低的缩写形式进行比较。在元组排序中，我们可以支持这一点，因为我们总是可以根据需要从元组中提取原始 datum。这里我们不能，因为 datum 排序只存储 datum 的单个副本；每个 SortTuple 的 "tuple" 字段为 NULL。
	 */
	fc_state->sortKeys->abbreviate = !fc_typbyval;

	PrepareSortSupportFromOrderingOp(fc_sortOperator, fc_state->sortKeys);

	/*
	 * "onlyKey" 优化不能与缩写键一起使用，因为
	 * 可能需要打破平局的比较。 通常，这种优化
	 * 对于按值传递的类型是有价值的，而缩写键通常
	 * 仅对按引用传递的类型有价值。
	 */
	if (!fc_state->sortKeys->abbrev_converter)
		fc_state->onlyKey = fc_state->sortKeys;

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_state;
}

/*
 * tuplesort_set_bound
 *
 *	建议 tuplesort 至多需要前 N 个结果元组。
 *
 * 必须在插入任何元组之前调用。 （实际上，我们可以允许它，只要排序尚未溢出到磁盘，但目前似乎没有延迟调用的必要。）
 *
 * 这只是一个提示。 tuplesort 仍然可能返回比请求更多的元组。并行领导者 tuplesorts 将始终忽略提示。
 */
void tuplesort_set_bound(Tuplesortstate *fc_state, int64 fc_bound)
{
	/* 断言我们在加载任何元组之前被调用 */
	Assert(fc_state->status == TSS_INITIAL && fc_state->memtupcount == 0);
	/* 断言我们允许有界排序 */
	Assert(fc_state->sortopt & TUPLESORT_ALLOWBOUNDED);
	/* 也不能两次设置界限 */
	Assert(!fc_state->bounded);
	/* 此外，这不应在并行工作者中调用 */
	Assert(!WORKER(fc_state));

	/* 并行领导者允许但忽略提示 */
	if (LEADER(fc_state))
		return;

#ifdef DEBUG_BOUNDED_SORT
	/* 尊重禁用功能的 GUC 设置（便于测试） */
	if (!optimize_bounded_sort)
		return;
#endif

	/* 我们希望能够计算界限 * 2，因此限制设置 */
	if (fc_bound > (int64) (INT_MAX / 2))
		return;

	fc_state->bounded = true;
	fc_state->bound = (int) fc_bound;

	/*
	 * 有界排序不是缩写键优化的有效目标。通过设置状态与没有缩写支持保持一致来禁用它。
	 */
	fc_state->sortKeys->abbrev_converter = NULL;
	if (fc_state->sortKeys->abbrev_full_comparator)
		fc_state->sortKeys->comparator = fc_state->sortKeys->abbrev_full_comparator;

	/* 严格来说不是必须的，但保持整洁 */
	fc_state->sortKeys->abbrev_abort = NULL;
	fc_state->sortKeys->abbrev_full_comparator = NULL;
}

/*
 * tuplesort_used_bound
 *
 * 允许调用者找出排序状态是否能够使用界限。
 */
bool tuplesort_used_bound(Tuplesortstate *fc_state)
{
	return fc_state->boundUsed;
}

/*
 * tuplesort_free
 *
 *	释放tuplesort的资源的内部例程。
 */
static void fc_tuplesort_free(Tuplesortstate *fc_state)
{
	/* 上下文交换可能不需要，但让我们小心点 */
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

#ifdef TRACE_SORT
	long		fc_spaceUsed;

	if (fc_state->tapeset)
		fc_spaceUsed = LogicalTapeSetBlocks(fc_state->tapeset);
	else
		fc_spaceUsed = (fc_state->allowedMem - fc_state->availMem + 1023) / 1024;
#endif

	/*
	 * 如果有的话，删除临时“磁带”文件。
	 *
	 * 注意：我们希望将其包含在报告的排序总成本中，因此需要
	 * 两个#ifdef TRACE_SORT部分。
	 *
	 * 在这里我们不打算销毁单独的磁带。它们将随着sortcontext一起消失。
	 * （在TSS_FINALMERGE状态下，我们已经关闭了完成的磁带。）
	 */
	if (fc_state->tapeset)
		LogicalTapeSetClose(fc_state->tapeset);

#ifdef TRACE_SORT
	if (trace_sort)
	{
		if (fc_state->tapeset)
			elog(LOG, "%s of worker %d ended, %ld disk blocks used: %s",
				 SERIAL(fc_state) ? "external sort" : "parallel external sort",
				 fc_state->worker, fc_spaceUsed, pg_rusage_show(&fc_state->ru_start));
		else
			elog(LOG, "%s of worker %d ended, %ld KB used: %s",
				 SERIAL(fc_state) ? "internal sort" : "unperformed parallel sort",
				 fc_state->worker, fc_spaceUsed, pg_rusage_show(&fc_state->ru_start));
	}

	TRACE_POSTGRESQL_SORT_DONE(fc_state->tapeset != NULL, spaceUsed);
#else

	/*
	 * 如果您禁用了TRACE_SORT，您仍然可以探测sort__done，但您
	 * 将无法获取空间使用统计信息。
	 */
	TRACE_POSTGRESQL_SORT_DONE(fc_state->tapeset != NULL, 0L);
#endif

	/* 释放为CLUSTER案例创建的任何执行状态 */
	if (fc_state->estate != NULL)
	{
		ExprContext *fc_econtext = GetPerTupleExprContext(fc_state->estate);

		ExecDropSingleTupleTableSlot(fc_econtext->ecxt_scantuple);
		FreeExecutorState(fc_state->estate);
	}

	MemoryContextSwitchTo(fc_oldcontext);

	/*
	 * 释放每次排序的内存上下文，从而释放所有工作内存。
	 */
	MemoryContextReset(fc_state->sortcontext);
}

/*
 * tuplesort_end
 *
 *	释放资源并进行清理。
 *
 * 注意：在调用此方法后，由tuplesort_getXXX返回的任何指针
 * 都指向垃圾。 请小心不要尝试在之后使用或释放此类指针！
 */
void tuplesort_end(Tuplesortstate *fc_state)
{
	fc_tuplesort_free(fc_state);

	/*
	 * 释放主内存上下文，包括Tuplesortstate结构
	 * 本身。
	 */
	MemoryContextDelete(fc_state->maincontext);
}

/*
 * tuplesort_updatemax
 *
 *	更新最大资源使用统计信息。
 */
static void fc_tuplesort_updatemax(Tuplesortstate *fc_state)
{
	int64		fc_spaceUsed;
	bool		fc_isSpaceDisk;

	/*
	 * 注意：在基于磁盘的排序中，似乎应该提供内存和磁盘使用情况。
	 * 然而，当前代码在开始将元组返回给调用者后并未准确追踪内存空间
	 * （因为我们没有考虑调用者预计要做的pfree），因此我们不能
	 * 在磁盘排序中依赖availMem。修复这个似乎不值得。
	 * 是否值得为内存上下文代码创建一个API，以告诉我们在sortcontext中
	 * 实际使用了多少？
	 */
	if (fc_state->tapeset)
	{
		fc_isSpaceDisk = true;
		fc_spaceUsed = LogicalTapeSetBlocks(fc_state->tapeset) * BLCKSZ;
	}
	else
	{
		fc_isSpaceDisk = false;
		fc_spaceUsed = fc_state->allowedMem - fc_state->availMem;
	}

	/*
	 * 当排序无法将数据放入主内存中时，排序将数据逐出到磁盘。
	 * 这就是为什么我们认为跟踪资源使用时磁盘上使用的空间比内存中
	 * 使用的空间更重要。请注意，某些tupleset在磁盘上占用的空间
	 * 可能少于相同tupleset在内存中占用的空间，这可能是由于更紧凑的表示。
	 */
	if ((fc_isSpaceDisk && !fc_state->isMaxSpaceDisk) ||
		(fc_isSpaceDisk == fc_state->isMaxSpaceDisk && fc_spaceUsed > fc_state->maxSpace))
	{
		fc_state->maxSpace = fc_spaceUsed;
		fc_state->isMaxSpaceDisk = fc_isSpaceDisk;
		fc_state->maxSpaceStatus = fc_state->status;
	}
}

/*
 * tuplesort_reset
 *
 *	重置tuplesort。重置tuplesort中的所有数据，但保留元
 *	信息。在tuplesort_reset之后，tuplesort准备开始
 *	新的排序。这可以避免在排序多个小批次时重新创建
 *	tuple排序状态（并节省资源）。
 */
void tuplesort_reset(Tuplesortstate *fc_state)
{
	fc_tuplesort_updatemax(fc_state);
	fc_tuplesort_free(fc_state);

	/*
	 * 在我们释放每批的内存后，重新设置第一次批处理和任何
	 * 后续批处理的所有共同状态。
	 */
	fc_tuplesort_begin_batch(fc_state);

	fc_state->lastReturnedTuple = NULL;
	fc_state->slabMemoryBegin = NULL;
	fc_state->slabMemoryEnd = NULL;
	fc_state->slabFreeHead = NULL;
}

/*
 * 如果可能的话，扩大 memtuples[] 数组，同时遵守我们的内存限制。
 * 我们不能超过内存中的 INT_MAX 个元组或调用者提供的内存限制。
 * 如果我们能够扩大数组，返回 true；否则返回 false。
 *
 * 通常，在每次增量时我们会将数组的大小加倍。当这样做会超过限制时，
 * 我们尝试最后一次较小的增加（然后清除 growmemtuples 标志，以便我们
 * 不再尝试）。这使我们能够充分利用内存；坚持纯粹的加倍规则可能会
 * 导致几乎一半的内存未被使用。由于 availMem 随着元组的增加/删除而
 * 变化，我们需要某种规则以防止在 memtupsize 中进行重复的小增加，
 * 这将无益于处理。growmemtuples 标志实现了这一点，并且还防止了该
 * 函数中的无用重计算。
 */
static bool fc_grow_memtuples(Tuplesortstate *fc_state)
{
	int			fc_newmemtupsize;
	int			fc_memtupsize = fc_state->memtupsize;
	int64		fc_memNowUsed = fc_state->allowedMem - fc_state->availMem;

	/* 如果我们已经用尽了 memtuples，请忘掉它，如上面的评论所述 */
	if (!fc_state->growmemtuples)
		return false;

	/* 选择 memtupsize 的新值 */
	if (fc_memNowUsed <= fc_state->availMem)
	{
		/*
		 * 我们使用的内存没有超过 allowedMem 的一半；将我们的使用量
		 * 翻倍，限制为 INT_MAX 个元组。
		 */
		if (fc_memtupsize < INT_MAX / 2)
			fc_newmemtupsize = fc_memtupsize * 2;
		else
		{
			fc_newmemtupsize = INT_MAX;
			fc_state->growmemtuples = false;
		}
	}
	else
	{
		/*
		 * 这将是 memtupsize 的最后一次增量。放弃加倍策略，而是尽
		 * 可能安全地增加。
		 *
		 * 为了在 allowedMem 范围内，我们不能将 memtupsize 增加超过
		 * availMem / sizeof(SortTuple) 个元素。在实践中，我们希望将其
		 * 增加得少一些，因为我们需要留出一些空间以供新数组槽引用的
		 * 元组。我们假设新元组的大小将和我们已经见过的元组大致相同，
		 * 因此我们可以根据到目前为止的空间消耗推断出 memtuples 数组
		 * 的适当新大小。最优值可能高于或低于这个估计，但很难提前知道。
		 * 我们再次限制为 INT_MAX 个元组。
		 *
		 * 这个计算是安全的，不会扩大数组到导致 LACKMEM 为 true，
		 * 因为当前使用的内存包括现有数组；因此，即使当前没有使用其他
		 * 内存，留给新数组元素的 allowedMem 也会足够。
		 *
		 * 我们在 float8 中做算术运算，因为否则 memtupsize 和 allowedMem
		 * 的乘积可能会溢出。结果的任何不准确性应该是微不足道的；但即使
		 * 我们计算出一个完全荒谬的结果，下面的检查也会防止发生真正糟糕的
		 * 事情。
		 */
		double		fc_grow_ratio;

		fc_grow_ratio = (double) fc_state->allowedMem / (double) fc_memNowUsed;
		if (fc_memtupsize * fc_grow_ratio < INT_MAX)
			fc_newmemtupsize = (int) (fc_memtupsize * fc_grow_ratio);
		else
			fc_newmemtupsize = INT_MAX;

		/* 我们不会进行任何进一步的扩大尝试 */
		fc_state->growmemtuples = false;
	}

	/* 必须至少扩大数组一个元素，否则报告失败 */
	if (fc_newmemtupsize <= fc_memtupsize)
		goto noalloc;

	/*
	 * 在 32 位机器上，allowedMem 可能超过 MaxAllocHugeSize。
	 * 限制以确保我们的请求不会被拒绝。请注意，我们可以很容易地
	 * 耗尽地址空间而不会面临这种结果。（目前由于 guc.c 的
	 * MAX_KILOBYTES 对 work_mem 的限制，这种情况是不可能的，
	 * 但在这个距离上不必依赖于此。）
	 */
	if ((Size) fc_newmemtupsize >= MaxAllocHugeSize / sizeof(SortTuple))
	{
		fc_newmemtupsize = (int) (MaxAllocHugeSize / sizeof(SortTuple));
		fc_state->growmemtuples = false;	/* 不能再增长了 */
	}

	/*
	 * 我们需要确保不造成 LACKMEM 为真，否则空间管理算法会失控。
	 * 上面的代码绝对不应该生成危险的请求，但为了安全起见，
	 * 明确检查数组增长是否在 availMem 范围内。 (如果与 memtuples
	 * 数组相关的内存块开销增加，我们仍然可能会导致 LACKMEM。
	 * 这不应该发生，因为我们选择的初始数组大小足够大，以确保
	 * palloc 会将旧数组和新数组视为独立块。但为了安全起见，
	 * 我们将在下面明确检查 LACKMEM。)
	 */
	if (fc_state->availMem < (int64) ((fc_newmemtupsize - fc_memtupsize) * sizeof(SortTuple)))
		goto noalloc;

	/* 注意：我们不在表达式树上标记排序规则 */
	FREEMEM(fc_state, GetMemoryChunkSpace(fc_state->memtuples));
	fc_state->memtupsize = fc_newmemtupsize;
	fc_state->memtuples = (SortTuple *)
		repalloc_huge(fc_state->memtuples,
					  fc_state->memtupsize * sizeof(SortTuple));
	USEMEM(fc_state, GetMemoryChunkSpace(fc_state->memtuples));
	if (LACKMEM(fc_state))
		elog(ERROR, "unexpected out-of-memory situation in tuplesort");
	return true;

noalloc:
	/* 如果出于任何原因我们没有重新分配，关闭未来的尝试 */
	fc_state->growmemtuples = false;
	return false;
}

/*
 * 在收集排序的输入数据时接受一个元组。
 *
 * 请注意，输入数据始终是被复制的；调用者不需要保存它。
 */
void tuplesort_puttupleslot(Tuplesortstate *fc_state, TupleTableSlot *fc_slot)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
	SortTuple	fc_stup;

	/*
	 * 将给定的元组复制到我们控制的内存中，并减少 availMem。
	 * 然后调用公共代码。
	 */
	COPYTUP(fc_state, &fc_stup, (void *) fc_slot);

	fc_puttuple_common(fc_state, &fc_stup);

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * 在收集排序的输入数据时接受一个元组。
 *
 * 请注意，输入数据始终是被复制的；调用者不需要保存它。
 */
void tuplesort_putheaptuple(Tuplesortstate *fc_state, HeapTuple fc_tup)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
	SortTuple	fc_stup;

	/*
	 * 将给定的元组复制到我们控制的内存中，并减少 availMem。
	 * 然后调用公共代码。
	 */
	COPYTUP(fc_state, &fc_stup, (void *) fc_tup);

	fc_puttuple_common(fc_state, &fc_stup);

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * 在收集排序的输入数据时接受一个索引元组，
 * 从调用者提供的值构建它。
 */
void tuplesort_putindextuplevalues(Tuplesortstate *fc_state, Relation fc_rel,
							  ItemPointer fc_self, Datum *fc_values,
							  bool *fc_isnull)
{
	MemoryContext fc_oldcontext;
	SortTuple	fc_stup;
	Datum		fc_original;
	IndexTuple	fc_tuple;

	fc_stup.tuple = index_form_tuple_context(RelationGetDescr(fc_rel), fc_values,
										  fc_isnull, fc_state->tuplecontext);
	fc_tuple = ((IndexTuple) fc_stup.tuple);
	fc_tuple->t_tid = *fc_self;
	USEMEM(fc_state, GetMemoryChunkSpace(fc_stup.tuple));
	/* 设置第一列键值 */
	fc_original = index_getattr(fc_tuple,
							 1,
							 RelationGetDescr(fc_state->indexRel),
							 &fc_stup.isnull1);

	fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

	if (!fc_state->sortKeys || !fc_state->sortKeys->abbrev_converter || fc_stup.isnull1)
	{
		/*
		 * 存储普通 Datum 表示，或 NULL 值。如果存在一个
		 * 转换器，它不会期望 NULL 值，且成本模型不
		 * 需要考虑 NULL，因此在这种情况下我们避免调用
		 * 转换器，并将 datum1 设置为零表示（为了保持一致
		 * 并支持对 NULL 缩略键的便宜不等式测试）。
		 */
		fc_stup.datum1 = fc_original;
	}
	else if (!fc_consider_abort_common(fc_state))
	{
		/* 存储缩略键表示 */
		fc_stup.datum1 = fc_state->sortKeys->abbrev_converter(fc_original,
														fc_state->sortKeys);
	}
	else
	{
		/* 中止缩略处理 */
		int			fc_i;

		fc_stup.datum1 = fc_original;

		/*
		 * 将状态设置为一致，以确保永远不会尝试缩略。
		 *
		 * 在已经复制的元组中更改 datum1 表示，以确保
		 * 一致的表示（当前元组刚刚处理）。如果某些转储的元组
		 * 已经在磁带上排序也没有关系，因为序列化的元组缺少
		 * 缩略键（TSS_BUILDRUNS 状态无论如何都会防止控制
		 * 达到这里）。
		 */
		for (fc_i = 0; fc_i < fc_state->memtupcount; fc_i++)
		{
			SortTuple  *fc_mtup = &fc_state->memtuples[fc_i];

			fc_tuple = fc_mtup->tuple;
			fc_mtup->datum1 = index_getattr(fc_tuple,
										 1,
										 RelationGetDescr(fc_state->indexRel),
										 &fc_mtup->isnull1);
		}
	}

	fc_puttuple_common(fc_state, &fc_stup);

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * 在收集排序的输入数据时接受一个 Datum。
 *
 * 如果 Datum 是传值类型，值将被复制。
 */
void tuplesort_putdatum(Tuplesortstate *fc_state, Datum fc_val, bool fc_isNull)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->tuplecontext);
	SortTuple	fc_stup;

	/*
	 * 传值类型或 NULL 值直接存储在 stup.datum1 中
	 * （并且 stup.tuple 没有被使用并设置为 NULL）。
	 *
	 * 非空的传引用值需要被复制到我们控制的内存中，
	 * 并可能被缩略。被复制的值由 stup.tuple 指向，
	 * 并被视为规范副本（例如，通过 tuplesort_getdatum 返回
	 * 或写入磁带时）；如果发生缩略，stup.datum1 将获得
	 * 缩略值，否则它与 stup.tuple 相同。
	 */

	if (fc_isNull || !fc_state->tuples)
	{
		/*
		 * 将datum1设置为零表示以便处理NULL（为了保持一致，
		 * 并支持对NULL缩略键的廉价不等式测试）。
		 */
		fc_stup.datum1 = !fc_isNull ? fc_val : (Datum) 0;
		fc_stup.isnull1 = fc_isNull;
		fc_stup.tuple = NULL;		/* 没有单独的存储 */
		MemoryContextSwitchTo(fc_state->sortcontext);
	}
	else
	{
		Datum		fc_original = datumCopy(fc_val, false, fc_state->datumTypeLen);

		fc_stup.isnull1 = false;
		fc_stup.tuple = DatumGetPointer(fc_original);
		USEMEM(fc_state, GetMemoryChunkSpace(fc_stup.tuple));
		MemoryContextSwitchTo(fc_state->sortcontext);

		if (!fc_state->sortKeys->abbrev_converter)
		{
			fc_stup.datum1 = fc_original;
		}
		else if (!fc_consider_abort_common(fc_state))
		{
			/* 存储缩略键表示 */
			fc_stup.datum1 = fc_state->sortKeys->abbrev_converter(fc_original,
															fc_state->sortKeys);
		}
		else
		{
			/* 中止缩略处理 */
			int			fc_i;

			fc_stup.datum1 = fc_original;

			/*
			 * 将状态设置为与从不尝试缩写保持一致。
			 *
			 * 在已经复制的元组中更改datum1的表示，以确保
			 * 一致的表示（当前元组刚刚处理过）。即使一些已转储的元组在磁带上
			 * 已经排序也无妨，因为序列化元组缺少缩略键
			 * （TSS_BUILDRUNS状态在任何情况下都阻止控制到达这里）。
			 */
			for (fc_i = 0; fc_i < fc_state->memtupcount; fc_i++)
			{
				SortTuple  *fc_mtup = &fc_state->memtuples[fc_i];

				fc_mtup->datum1 = PointerGetDatum(fc_mtup->tuple);
			}
		}
	}

	fc_puttuple_common(fc_state, &fc_stup);

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * 元组和数据案例的共享代码。
 */
static void fc_puttuple_common(Tuplesortstate *fc_state, SortTuple *fc_tuple)
{
	Assert(!LEADER(fc_state));

	switch (fc_state->status)
	{
		case TSS_INITIAL:

			/*
			 * 将元组保存到未排序数组中。首先，根据需要扩展数组。
			 * 注意，我们会在仍有一个空槽位时尝试扩展数组——如果失败，
			 * 仍然有空间存储传入元组，然后我们将切换到
			 * 基于磁带的操作。
			 */
			if (fc_state->memtupcount >= fc_state->memtupsize - 1)
			{
				(void) fc_grow_memtuples(fc_state);
				Assert(fc_state->memtupcount < fc_state->memtupsize);
			}
			fc_state->memtuples[fc_state->memtupcount++] = *fc_tuple;

			/*
			 * 检查是否是切换到有界堆排序的时候。如果输入元组数量超过
			 * 所需元组数量的两倍（这是一个关于堆排序比快速排序便宜的启发式），
			 * 或者如果我们刚刚填满了workMem并且有足够的元组
			 * 来满足界限。
			 *
			 * 注意，一旦我们进入TSS_BOUNDED状态，我们将始终尝试
			 * 以这种方式完成排序。在最坏的情况下，如果后来的输入
			 * 元组大于早期的元组，这可能会导致我们显著超过workMem。
			 */
			if (fc_state->bounded &&
				(fc_state->memtupcount > fc_state->bound * 2 ||
				 (fc_state->memtupcount > fc_state->bound && LACKMEM(fc_state))))
			{
#ifdef TRACE_SORT
				if (trace_sort)
					elog(LOG, "switching to bounded heapsort at %d tuples: %s",
						 fc_state->memtupcount,
						 pg_rusage_show(&fc_state->ru_start));
#endif
				fc_make_bounded_heap(fc_state);
				return;
			}

			/*
			 * 如果我们仍然适合可用内存并且有数组槽，完成。
			 */
			if (fc_state->memtupcount < fc_state->memtupsize && !LACKMEM(fc_state))
				return;

			/*
			 * 不行；是时候切换到基于磁带的操作了。
			 */
			fc_inittapes(fc_state, true);

			/*
			 * 转储所有元组。
			 */
			fc_dumptuples(fc_state, false);
			break;

		case TSS_BOUNDED:

			/*
			 * 我们不想在这里扩展数组，因此在放入新元组之前
			 * 检查是否可以丢弃它。这应该是一种良好的速度优化，
			 * 因为当输入元组数量远超过界限时，大多数输入元组
			 * 可以通过这一次比较直接被丢弃。请注意，由于我们当前
			 * 已经反转了排序方向，必须检查<=而不是>=。
			 */
			if (COMPARETUP(fc_state, fc_tuple, &fc_state->memtuples[0]) <= 0)
			{
				/* 新元组 <= 堆顶，因此我们可以丢弃它 */
				fc_free_sort_tuple(fc_state, fc_tuple);
				CHECK_FOR_INTERRUPTS();
			}
			else
			{
				/* 丢弃堆顶，以新元组替换它 */
				fc_free_sort_tuple(fc_state, &fc_state->memtuples[0]);
				fc_tuplesort_heap_replace_top(fc_state, fc_tuple);
			}
			break;

		case TSS_BUILDRUNS:

			/*
			 * 将元组保存到未排序数组中（必须有空间）
			 */
			fc_state->memtuples[fc_state->memtupcount++] = *fc_tuple;

			/*
			 * 如果我们超过了内存限制，转储所有元组。
			 */
			fc_dumptuples(fc_state, false);
			break;

		default:
			elog(ERROR, "invalid tuplesort state");
			break;
	}
}

static bool fc_consider_abort_common(Tuplesortstate *fc_state)
{
	Assert(fc_state->sortKeys[0].abbrev_converter != NULL);
	Assert(fc_state->sortKeys[0].abbrev_abort != NULL);
	Assert(fc_state->sortKeys[0].abbrev_full_comparator != NULL);

	/*
	 * 检查缩写优化的有效性。在仍在内存限制内时考虑中止。
	 */
	if (fc_state->status == TSS_INITIAL &&
		fc_state->memtupcount >= fc_state->abbrevNext)
	{
		fc_state->abbrevNext *= 2;

		/*
		 * 检查opclass提供的缩写中止例程。它可能表明
		 * 不应该进行缩写。
		 */
		if (!fc_state->sortKeys->abbrev_abort(fc_state->memtupcount,
										   fc_state->sortKeys))
			return false;

		/*
		 * 最后，恢复权威比较器，并通过将abbrev_converter设置为NULL
		 * 表示不进行缩写
		 */
		fc_state->sortKeys[0].comparator = fc_state->sortKeys[0].abbrev_full_comparator;
		fc_state->sortKeys[0].abbrev_converter = NULL;
		/* 严格来说不是必须的，但保持整洁 */
		fc_state->sortKeys[0].abbrev_abort = NULL;
		fc_state->sortKeys[0].abbrev_full_comparator = NULL;

		/* 放弃 - 期望原始的值传递表示 */
		return true;
	}

	return false;
}

/*
 * 所有元组已提供；完成排序。
 */
void tuplesort_performsort(Tuplesortstate *fc_state)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG, "performsort of worker %d starting: %s",
			 fc_state->worker, pg_rusage_show(&fc_state->ru_start));
#endif

	switch (fc_state->status)
	{
		case TSS_INITIAL:

			/*
			 * 我们能够在允许的内存量内积累所有元组，
			 * 或者由主控接管工作者带。
 */
			if (SERIAL(fc_state))
			{
				/* 只需对它们进行快速排序，我们就完成了 */
				fc_tuplesort_sort_memtuples(fc_state);
				fc_state->status = TSS_SORTEDINMEM;
			}
			else if (WORKER(fc_state))
			{
				/*
				 * 并行工作者仍然必须将元组转储到磁带。 但不需要
				 * 合并以产生单个输出运行。
				 */
				fc_inittapes(fc_state, false);
				fc_dumptuples(fc_state, true);
				fc_worker_nomergeruns(fc_state);
				fc_state->status = TSS_SORTEDONTAPE;
			}
			else
			{
				/*
				 * 主控将接管工作者的磁带并合并工作者的运行。
				 * 注意，合并运行设置了正确的状态->状态。
				 */
				fc_leader_takeover_tapes(fc_state);
				fc_mergeruns(fc_state);
			}
			fc_state->current = 0;
			fc_state->eof_reached = false;
			fc_state->markpos_block = 0L;
			fc_state->markpos_offset = 0;
			fc_state->markpos_eof = false;
			break;

		case TSS_BOUNDED:

			/*
			 * 我们能够在内存中积累输出所需的所有元组，
			 * 使用堆来消除多余的元组。 现在我们
			 * 必须将堆转换为正确排序的数组。
			 */
			fc_sort_bounded_heap(fc_state);
			fc_state->current = 0;
			fc_state->eof_reached = false;
			fc_state->markpos_offset = 0;
			fc_state->markpos_eof = false;
			fc_state->status = TSS_SORTEDINMEM;
			break;

		case TSS_BUILDRUNS:

			/*
			 * 完成基于磁带的排序。 首先，将内存中剩余的所有
			 * 元组刷新到磁带; 然后合并，直到我们只有一个剩余的
			 * 运行（或者，如果!randomAccess 和 !WORKER()，每个磁带一个运行）。
			 * 注意，合并运行设置了正确的状态->状态。
			 */
			fc_dumptuples(fc_state, true);
			fc_mergeruns(fc_state);
			fc_state->eof_reached = false;
			fc_state->markpos_block = 0L;
			fc_state->markpos_offset = 0;
			fc_state->markpos_eof = false;
			break;

		default:
			elog(ERROR, "invalid tuplesort state");
			break;
	}

#ifdef TRACE_SORT
	if (trace_sort)
	{
		if (fc_state->status == TSS_FINALMERGE)
			elog(LOG, "performsort of worker %d done (except %d-way final merge): %s",
				 fc_state->worker, fc_state->nInputTapes,
				 pg_rusage_show(&fc_state->ru_start));
		else
			elog(LOG, "performsort of worker %d done: %s",
				 fc_state->worker, pg_rusage_show(&fc_state->ru_start));
	}
#endif

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * 内部例程，以获取下一个元组，可以在前进或后退
 * 方向上进入 *stup。 如果没有更多元组，则返回 false。
 * 返回的元组属于元组排序内存上下文，调用者不得释放。
 * 注意，获取的元组存储在可能被
 * 任何未来获取回收的内存中。
 */
static bool fc_tuplesort_gettuple_common(Tuplesortstate *fc_state, bool fc_forward,
						  SortTuple *fc_stup)
{
	unsigned int fc_tuplen;
	size_t		fc_nmoved;

	Assert(!WORKER(fc_state));

	switch (fc_state->status)
	{
		case TSS_SORTEDINMEM:
			Assert(fc_forward || fc_state->sortopt & TUPLESORT_RANDOMACCESS);
			Assert(!fc_state->slabAllocatorUsed);
			if (fc_forward)
			{
				if (fc_state->current < fc_state->memtupcount)
				{
					*fc_stup = fc_state->memtuples[fc_state->current++];
					return true;
				}
				fc_state->eof_reached = true;

				/*
				 * 如果调用者尝试在有边界的排序中检索比
				 * 最初请求的更多元组，则进行抱怨。 这是因为
				 * 在这里返回 EOF 可能是不正确的做法。
				 */
				if (fc_state->bounded && fc_state->current >= fc_state->bound)
					elog(ERROR, "retrieved too many tuples in a bounded sort");

				return false;
			}
			else
			{
				if (fc_state->current <= 0)
					return false;

				/*
				 * 如果已经获取了所有元组，则返回最后一个
				 * 元组，否则 - 返回倒数第二个元组。
				 */
				if (fc_state->eof_reached)
					fc_state->eof_reached = false;
				else
				{
					fc_state->current--;	/* 最近返回的元组 */
					if (fc_state->current <= 0)
						return false;
				}
				*fc_stup = fc_state->memtuples[fc_state->current - 1];
				return true;
			}
			break;

		case TSS_SORTEDONTAPE:
			Assert(fc_forward || fc_state->sortopt & TUPLESORT_RANDOMACCESS);
			Assert(fc_state->slabAllocatorUsed);

			/*
			 * 在上一个 gettuple 调用中返回的元组所占用的槽
			 * 现在可以重用。
			 */
			if (fc_state->lastReturnedTuple)
			{
				RELEASE_SLAB_SLOT(fc_state, fc_state->lastReturnedTuple);
				fc_state->lastReturnedTuple = NULL;
			}

			if (fc_forward)
			{
				if (fc_state->eof_reached)
					return false;

				if ((fc_tuplen = fc_getlen(fc_state->result_tape, true)) != 0)
				{
					READTUP(fc_state, fc_stup, fc_state->result_tape, fc_tuplen);

					/*
					 * 记住我们返回的元组，以便在下次调用时可以回收
					 * 其内存。 （在 !state->tuples 的情况下，这可以是 NULL）。
					 */
					fc_state->lastReturnedTuple = fc_stup->tuple;

					return true;
				}
				else
				{
					fc_state->eof_reached = true;
					return false;
				}
			}

			/*
			 * 向后。
			 *
			 * 如果已经获取了所有元组，则返回最后一个元组，
			 * 否则 - 返回倒数第二个元组。
			 */
			if (fc_state->eof_reached)
			{
				/*
				 * 寻找位置刚好指向文件末尾的零元组后面； 向后
				 * 获取最后一个元组的结束长度单词。 如果寻址失败，我们
				 * 必须有一个完全空的文件。
				 */
				fc_nmoved = LogicalTapeBackspace(fc_state->result_tape,
											  2 * sizeof(unsigned int));
				if (fc_nmoved == 0)
					return false;
				else if (fc_nmoved != 2 * sizeof(unsigned int))
					elog(ERROR, "unexpected tape position");
				fc_state->eof_reached = false;
			}
			else
			{
				/*
				 * 向后并获取先前返回的元组的结束长度
				 * 单词。 如果寻址失败，假定我们位于文件开头。
				 */
				fc_nmoved = LogicalTapeBackspace(fc_state->result_tape,
											  sizeof(unsigned int));
				if (fc_nmoved == 0)
					return false;
				else if (fc_nmoved != sizeof(unsigned int))
					elog(ERROR, "unexpected tape position");
				fc_tuplen = fc_getlen(fc_state->result_tape, false);

				/*
				 * 向后获取其前面的元组的结束长度单词。
				 */
				fc_nmoved = LogicalTapeBackspace(fc_state->result_tape,
											  fc_tuplen + 2 * sizeof(unsigned int));
				if (fc_nmoved == fc_tuplen + sizeof(unsigned int))
				{
					/*
					 * 我们向后越过先前的元组，但在它之前没有
					 * 结束长度单词。 这意味着上一个
					 * 元组是文件中的第一个元组。 它现在是
					 * 下一步在前进方向上读取的元组（这并不明显正确，
					 * 但这就是内存案例所做的）。
					 */
					return false;
				}
				else if (fc_nmoved != fc_tuplen + 2 * sizeof(unsigned int))
					elog(ERROR, "bogus tuple length in backward scan");
			}

			fc_tuplen = fc_getlen(fc_state->result_tape, false);

			/*
			 * 现在我们有了前一个元组的长度，回退并读取它。
			 * 注意：READTUP 期望我们位于元组的初始长度词之后，所以回退到那个点。
			 */
			fc_nmoved = LogicalTapeBackspace(fc_state->result_tape,
										  fc_tuplen);
			if (fc_nmoved != fc_tuplen)
				elog(ERROR, "bogus tuple length in backward scan");
			READTUP(fc_state, fc_stup, fc_state->result_tape, fc_tuplen);

			/*
			 * 记住我们返回的元组，以便在下一次调用时可以回收它的内存。
			 * （在 Datum 情况下，这可以是 NULL）。
			 */
			fc_state->lastReturnedTuple = fc_stup->tuple;

			return true;

		case TSS_FINALMERGE:
			Assert(fc_forward);
			/* 我们自己管理内存，使用 slab 分配器。 */
			Assert(fc_state->slabAllocatorUsed);

			/*
			 * 保存上一次 gettuple 调用中返回的元组的 slab 插槽现在可以重用。
			 */
			if (fc_state->lastReturnedTuple)
			{
				RELEASE_SLAB_SLOT(fc_state, fc_state->lastReturnedTuple);
				fc_state->lastReturnedTuple = NULL;
			}

			/*
			 * 这段代码应该与 mergeonerun() 的内部循环相匹配。
			 */
			if (fc_state->memtupcount > 0)
			{
				int			fc_srcTapeIndex = fc_state->memtuples[0].srctape;
				LogicalTape *fc_srcTape = fc_state->inputTapes[fc_srcTapeIndex];
				SortTuple	fc_newtup;

				*fc_stup = fc_state->memtuples[0];

				/*
				 * 记住我们返回的元组，以便在下一次调用时可以回收它的内存。
				 * （在 Datum 情况下，这可以是 NULL）。
				 */
				fc_state->lastReturnedTuple = fc_stup->tuple;

				/*
				 * 从磁带中提取下一个元组，并用它替换堆顶返回的元组。
				 */
				if (!fc_mergereadnext(fc_state, fc_srcTape, &fc_newtup))
				{
					/*
					 * 如果没有更多数据，我们已到达此磁带的运行末尾。
					 * 从堆中移除顶部节点。
					 */
					fc_tuplesort_heap_delete_top(fc_state);
					fc_state->nInputRuns--;

					/*
					 * 关闭磁带。它在排序结束时会消失，但最好提前释放内存。
					 */
					LogicalTapeClose(fc_srcTape);
					return true;
				}
				fc_newtup.srctape = fc_srcTapeIndex;
				fc_tuplesort_heap_replace_top(fc_state, &fc_newtup);
				return true;
			}
			return false;

		default:
			elog(ERROR, "invalid tuplesort state");
			return false;		/* 保持编译器安静 */
	}
}

/*
 * 在前进或后退方向上获取下一个元组。
 * 如果成功，将元组放入插槽并返回 true；否则，清除插槽并返回 false。
 *
 * 调用者在使用缩写时可以选择在 true 返回值时传回缩写值，
 * 这可以用来便宜地避免可能需要的相等性检查。
 * 调用者可以安全地根据简单的二元不等式来判断“非相等元组”。
 * 如果主属性中的 NULL 值将缩写值设置为零表示，
 * 调用者可以在缩写不等式检查中依赖它。
 *
 * 如果 copy 为 true，插槽接收一个已经复制到调用者内存上下文中的元组，
 * 这样它将保持有效，无论将来如何操作元组排序的状态
 * （包括删除元组排序）。如果 copy 为 false，插槽将只接收一个
 * 指向在元组排序中持有的元组的指针，这更加高效，但仅对
 * 准备好在以后任何操作中使元组排序状态无效的调用者安全。
 */
bool tuplesort_gettupleslot(Tuplesortstate *fc_state, bool fc_forward, bool fc_copy,
					   TupleTableSlot *fc_slot, Datum *fc_abbrev)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
	SortTuple	fc_stup;

	if (!fc_tuplesort_gettuple_common(fc_state, fc_forward, &fc_stup))
		fc_stup.tuple = NULL;

	MemoryContextSwitchTo(fc_oldcontext);

	if (fc_stup.tuple)
	{
		/* 记录给调用者的缩写键 */
		if (fc_state->sortKeys->abbrev_converter && fc_abbrev)
			*fc_abbrev = fc_stup.datum1;

		if (fc_copy)
			fc_stup.tuple = heap_copy_minimal_tuple((MinimalTuple) fc_stup.tuple);

		ExecStoreMinimalTuple((MinimalTuple) fc_stup.tuple, fc_slot, fc_copy);
		return true;
	}
	else
	{
		ExecClearTuple(fc_slot);
		return false;
	}
}

/*
 * 在前进或后退方向上获取下一个元组。
 * 如果没有更多元组则返回 NULL。返回的元组属于元组排序内存
 * 上下文，调用者不得释放它。调用者不得依赖元组
 * 在进一步操作元组排序后保持有效。
 */
HeapTuple tuplesort_getheaptuple(Tuplesortstate *fc_state, bool fc_forward)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
	SortTuple	fc_stup;

	if (!fc_tuplesort_gettuple_common(fc_state, fc_forward, &fc_stup))
		fc_stup.tuple = NULL;

	MemoryContextSwitchTo(fc_oldcontext);

	return fc_stup.tuple;
}

/*
 * 在前进或后退方向上获取下一个索引元组。
 * 如果没有更多元组则返回 NULL。返回的元组属于元组排序内存
 * 上下文，调用者不得释放它。调用者不得依赖元组
 * 在进一步操作元组排序后保持有效。
 */
IndexTuple tuplesort_getindextuple(Tuplesortstate *fc_state, bool fc_forward)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
	SortTuple	fc_stup;

	if (!fc_tuplesort_gettuple_common(fc_state, fc_forward, &fc_stup))
		fc_stup.tuple = NULL;

	MemoryContextSwitchTo(fc_oldcontext);

	return (IndexTuple) fc_stup.tuple;
}

/*
 * 获取下一个 Datum，方向可以是向前或向后。
 * 如果没有更多数据，将返回 false。
 *
 * 如果 Datum 是按引用传递类型，则返回的值是在调用者的上下文中
 * 新分配的 palloc'd，并且现在由调用者拥有（与其他类型的 tuplesorts
 * 的类似例程不同）。
 *
 * 当使用缩写时，调用者可以选择在返回 true 时传回缩写值，
 * 可以用来便宜地避免可能需要的相等性检查。调用者可以安全地基于
 * 简单的二元不等式来判断“非相等元组”。一个 NULL 值将具有
 * 零值的缩写值表示，调用者可以在缩写不等式检查中依赖于此。
 */
bool tuplesort_getdatum(Tuplesortstate *fc_state, bool fc_forward,
				   Datum *fc_val, bool *fc_isNull, Datum *fc_abbrev)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
	SortTuple	fc_stup;

	if (!fc_tuplesort_gettuple_common(fc_state, fc_forward, &fc_stup))
	{
		MemoryContextSwitchTo(fc_oldcontext);
		return false;
	}

	/* 确保我们复制到调用者的内存上下文 */
	MemoryContextSwitchTo(fc_oldcontext);

	/* 记录给调用者的缩写键 */
	if (fc_state->sortKeys->abbrev_converter && fc_abbrev)
		*fc_abbrev = fc_stup.datum1;

	if (fc_stup.isnull1 || !fc_state->tuples)
	{
		*fc_val = fc_stup.datum1;
		*fc_isNull = fc_stup.isnull1;
	}
	else
	{
		/* 使用 stup.tuple，因为 stup.datum1 可能是缩写 */
		*fc_val = datumCopy(PointerGetDatum(fc_stup.tuple), false, fc_state->datumTypeLen);
		*fc_isNull = false;
	}

	return true;
}

/*
 * 在前进或后退方向上跳过 N 个元组，
 * 不返回任何数据。N==0 是一个无操作。
 * 如果成功则返回 true，若元组用尽则返回 false。
 */
bool tuplesort_skiptuples(Tuplesortstate *fc_state, int64 fc_ntuples, bool fc_forward)
{
	MemoryContext fc_oldcontext;

	/*
	 * 我们实际上还不支持向后跳过，因为没有调用者需要
	 * 它。不过，该 API 设计允许将来支持。
	 */
	Assert(fc_forward);
	Assert(fc_ntuples >= 0);
	Assert(!WORKER(fc_state));

	switch (fc_state->status)
	{
		case TSS_SORTEDINMEM:
			if (fc_state->memtupcount - fc_state->current >= fc_ntuples)
			{
				fc_state->current += fc_ntuples;
				return true;
			}
			fc_state->current = fc_state->memtupcount;
			fc_state->eof_reached = true;

			/*
			 * 如果调用者尝试检索比在有界排序中原始请求更多的元组，
			 * 则抱怨。这是因为在这里返回 EOF 可能是不正确的。
			 */
			if (fc_state->bounded && fc_state->current >= fc_state->bound)
				elog(ERROR, "retrieved too many tuples in a bounded sort");

			return false;

		case TSS_SORTEDONTAPE:
		case TSS_FINALMERGE:

			/*
			 * 我们可能可以更好地优化这些情况，但目前这
			 * 还不值得麻烦。
			 */
			fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);
			while (fc_ntuples-- > 0)
			{
				SortTuple	fc_stup;

				if (!fc_tuplesort_gettuple_common(fc_state, fc_forward, &fc_stup))
				{
					MemoryContextSwitchTo(fc_oldcontext);
					return false;
				}
				CHECK_FOR_INTERRUPTS();
			}
			MemoryContextSwitchTo(fc_oldcontext);
			return true;

		default:
			elog(ERROR, "invalid tuplesort state");
			return false;		/* 保持编译器安静 */
	}
}

/*
 * tuplesort_merge_order - 报告我们将在给定内存
 * （注意："合并顺序"只是指合并中的输入带数量）中使用的合并顺序。
 *
 * 这对规划器是公开的。allowedMem 以字节为单位。
 */
int tuplesort_merge_order(int64 fc_allowedMem)
{
	int			fc_mOrder;

	/*----------
	 * 在合并阶段，我们需要为每个输入和输出带提供缓冲空间。
	 * 平衡合并算法中的每次传递从 M 个输入带读取，并
	 * 写入 N 个输出带。每个带消耗 TAPE_BUFFER_OVERHEAD 字节
	 * 的内存。除此之外，我们还想为每个输入带提供 MERGE_BUFFER_SIZE
	 * 的工作空间。
	 *
	 * totalMem = M * (TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE) +
	 *            N * TAPE_BUFFER_OVERHEAD
	 *
	 * 除最后一次和倒数第二次合并传递外，在那里可以有
	 * 更少的带需要处理，M = N。我们选择 M，以便为
	 * 输入缓冲区（TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE）提供
	 * 所需的内存量，考虑到带缓冲区的总内存（allowedMem）。
	 *
	 * 注意：你可能会认为我们需要在此计算中考虑 memtuples[]
	 * 数组，但我们实际上将其视为 MERGE_BUFFER_SIZE 工作空间的一部分。
	 *----------
	 */
	fc_mOrder = fc_allowedMem /
		(2 * TAPE_BUFFER_OVERHEAD + MERGE_BUFFER_SIZE);

	/*
	 * 即使在最低内存情况下，至少使用 MINORDER 合并。另一方面，即使我们有很多内存，也不要使用超过 MAXORDER 的合并。磁带相当便宜，但并不是完全免费的。每增加一个磁带就会减少可用于构建运行的内存，这反过来可能导致相同的排序需要更多的运行，从而使合并变慢，即使它仍可以在一次通过中完成。此外，高阶合并由于 CPU 缓存效应相当缓慢；与在数百个磁带上执行单次合并相比，进行多次传输合并的 I/O 成本可能更快。
	 */
	fc_mOrder = Max(fc_mOrder, MINORDER);
	fc_mOrder = Min(fc_mOrder, MAXORDER);

	return fc_mOrder;
}

/*
 * 辅助函数，用于计算在合并过程中为每个输入磁带的读取缓冲区分配多少内存。
 *
 * 'avail_mem' 是所有磁带（输入和输出）缓冲区可用的内存量。
 * 'nInputTapes' 和 'nInputRuns' 是输入磁带和运行的数量。
 * 'maxOutputTapes' 是我们应该生成的最大输出磁带数量。
 */
static int64 fc_merge_read_buffer_size(int64 fc_avail_mem, int fc_nInputTapes, int fc_nInputRuns,
					   int fc_maxOutputTapes)
{
	int			fc_nOutputRuns;
	int			fc_nOutputTapes;

	/*
	 * 在这一轮中，我们将产生多少个输出磁带？
	 *
	 * 这是 nInputRuns / nInputTapes，向上取整。
	 */
	fc_nOutputRuns = (fc_nInputRuns + fc_nInputTapes - 1) / fc_nInputTapes;

	fc_nOutputTapes = Min(fc_nOutputRuns, fc_maxOutputTapes);

	/*
	 * 每个输出磁带消耗 TAPE_BUFFER_OVERHEAD 字节的内存。所有剩余的内存在输入磁带之间平均分配。
	 *
	 * 这也遵循 tuplesort_merge_order 中的公式，但在这里我们从可用的内存、M 和 N 中推导输入缓冲区的大小。
	 */
	return Max((fc_avail_mem - TAPE_BUFFER_OVERHEAD * fc_nOutputTapes) / fc_nInputTapes, 0);
}

/*
 * inittapes - 初始化磁带排序。
 *
 * 仅在我们发现不会在内存中进行排序时调用。
 */
static void fc_inittapes(Tuplesortstate *fc_state, bool fc_mergeruns)
{
	Assert(!LEADER(fc_state));

	if (fc_mergeruns)
	{
		/* 计算合并时要使用的输入磁带数量 */
		fc_state->maxTapes = tuplesort_merge_order(fc_state->allowedMem);
	}
	else
	{
		/* 工作线程有时可以产生单个运行，输出无需合并 */
		Assert(WORKER(fc_state));
		fc_state->maxTapes = MINORDER;
	}

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG, "worker %d switching to external sort with %d tapes: %s",
			 fc_state->worker, fc_state->maxTapes, pg_rusage_show(&fc_state->ru_start));
#endif

	/* 创建磁带集 */
	fc_inittapestate(fc_state, fc_state->maxTapes);
	fc_state->tapeset =
		LogicalTapeSetCreate(false,
							 fc_state->shared ? &fc_state->shared->fileset : NULL,
							 fc_state->worker);

	fc_state->currentRun = 0;

	/*
	 * 初始化逻辑磁带数组。
	 */
	fc_state->inputTapes = NULL;
	fc_state->nInputTapes = 0;
	fc_state->nInputRuns = 0;

	fc_state->outputTapes = palloc0(fc_state->maxTapes * sizeof(LogicalTape *));
	fc_state->nOutputTapes = 0;
	fc_state->nOutputRuns = 0;

	fc_state->status = TSS_BUILDRUNS;

	fc_selectnewtape(fc_state);
}

/*
 * inittapestate - 初始化通用的磁带管理状态
 */
static void fc_inittapestate(Tuplesortstate *fc_state, int fc_maxTapes)
{
	int64		fc_tapeSpace;

	/*
	 * 减少 availMem 以反映磁带缓冲区所需的空间；但不要减少到没有容纳元组的空间。（这种情况仅可能发生在按值排序的 Datums；在所有其他情况下，memtuples[] 数组不太可能占用超过 allowedMem 一半的空间。在按值传递的情况下，考虑元组空间并不重要，因此我们不在乎是否 LACKMEM 变得不准确。）
	 */
	fc_tapeSpace = (int64) fc_maxTapes * TAPE_BUFFER_OVERHEAD;

	if (fc_tapeSpace + GetMemoryChunkSpace(fc_state->memtuples) < fc_state->allowedMem)
		USEMEM(fc_state, fc_tapeSpace);

	/*
	 * 确保支持磁带集的临时文件在合适的临时表空间中创建。对于并行排序，这应该已经被调用，但如果第二次调用也无妨。
	 */
	PrepareTempTablespaces();
}

/*
 * selectnewtape -- 选择下一个要输出的磁带。
 *
 * 在我们知道必须开始另一个运行时，这在完成一个运行后调用。用于构建初始运行和合并过程中的运行。
 */
static void fc_selectnewtape(Tuplesortstate *fc_state)
{
	/*
	 * 在每次合并过程中，nOutputTapes 和 nOutputRuns 都为零。每次调用时，我们创建一个新的输出带来保存下一个运行，直到达到 maxTapes。之后，我们以轮询的方式将新的运行分配给现有的带。
	 */
	if (fc_state->nOutputTapes < fc_state->maxTapes)
	{
		/* 创建一个新的带来保存下一个运行 */
		Assert(fc_state->outputTapes[fc_state->nOutputRuns] == NULL);
		Assert(fc_state->nOutputRuns == fc_state->nOutputTapes);
		fc_state->destTape = LogicalTapeCreate(fc_state->tapeset);
		fc_state->outputTapes[fc_state->nOutputTapes] = fc_state->destTape;
		fc_state->nOutputTapes++;
		fc_state->nOutputRuns++;
	}
	else
	{
		/*
		 * 我们已达到带的最大数量。附加到现有带上。
		 */
		fc_state->destTape = fc_state->outputTapes[fc_state->nOutputRuns % fc_state->nOutputTapes];
		fc_state->nOutputRuns++;
	}
}

/*
 * 初始化 slab 分配区，用于给定数量的槽位。
 */
static void fc_init_slab_allocator(Tuplesortstate *fc_state, int fc_numSlots)
{
	if (fc_numSlots > 0)
	{
		char	   *fc_p;
		int			fc_i;

		fc_state->slabMemoryBegin = palloc(fc_numSlots * SLAB_SLOT_SIZE);
		fc_state->slabMemoryEnd = fc_state->slabMemoryBegin +
			fc_numSlots * SLAB_SLOT_SIZE;
		fc_state->slabFreeHead = (SlabSlot *) fc_state->slabMemoryBegin;
		USEMEM(fc_state, fc_numSlots * SLAB_SLOT_SIZE);

		fc_p = fc_state->slabMemoryBegin;
		for (fc_i = 0; fc_i < fc_numSlots - 1; fc_i++)
		{
			((SlabSlot *) fc_p)->nextfree = (SlabSlot *) (fc_p + SLAB_SLOT_SIZE);
			fc_p += SLAB_SLOT_SIZE;
		}
		((SlabSlot *) fc_p)->nextfree = NULL;
	}
	else
	{
		fc_state->slabMemoryBegin = fc_state->slabMemoryEnd = NULL;
		fc_state->slabFreeHead = NULL;
	}
	fc_state->slabAllocatorUsed = true;
}

/*
 * mergeruns -- 合并所有已完成的初始运行。
 *
 * 这实现了平衡的 k-way 合并算法。所有输入数据已经写入带上的初始运行（参见 dumptuples）。
 */
static void fc_mergeruns(Tuplesortstate *fc_state)
{
	int			fc_tapenum;

	Assert(fc_state->status == TSS_BUILDRUNS);
	Assert(fc_state->memtupcount == 0);

	if (fc_state->sortKeys != NULL && fc_state->sortKeys->abbrev_converter != NULL)
	{
		/*
		 * 如果有多个运行需要合并，当我们从磁盘读取元组时，缩写键将不会被存储，我们也不关心重新生成它们。从这一点开始禁用缩写。
		 */
		fc_state->sortKeys->abbrev_converter = NULL;
		fc_state->sortKeys->comparator = fc_state->sortKeys->abbrev_full_comparator;

		/* 严格来说不是必须的，但保持整洁 */
		fc_state->sortKeys->abbrev_abort = NULL;
		fc_state->sortKeys->abbrev_full_comparator = NULL;
	}

	/*
	 * 重置元组内存。我们已释放之前分配的所有元组。我们将从现在开始使用 slab 分配器。
	 */
	MemoryContextResetOnly(fc_state->tuplecontext);

	/*
	 * 我们不再需要一个大的 memtuples 数组。（稍后我们会为堆分配一个更小的数组。）
	 */
	FREEMEM(fc_state, GetMemoryChunkSpace(fc_state->memtuples));
	pfree(fc_state->memtuples);
	fc_state->memtuples = NULL;

	/*
	 * 初始化 slab 分配器。我们需要每个输入带一个 slab 槽，用于堆中的元组，加上一个槽用于保存最后从 tuplesort_gettuple 返回的元组。（如果我们在按值排序 Datums，则不需要分配任何东西。）
	 *
	 * 在多次合并中，如果最后一次合并的带数少于之前的合并，我们可以缩小这次分配，但我们不去做。
	 *
	 * 从这一点开始，我们不再使用 USEMEM()/LACKMEM() 机制来跟踪单个元组的内存使用情况。
	 */
	if (fc_state->tuples)
		fc_init_slab_allocator(fc_state, fc_state->nOutputTapes + 1);
	else
		fc_init_slab_allocator(fc_state, 0);

	/*
	 * 为堆分配一个新的 'memtuples' 数组。它将保存来自每个输入带的一个元组。
	 *
	 * 我们也可以在多次合并的过程中缩小这一点，但我们不去做。（初始输入带仍在 outputTapes 中。输入带的数量在合并过程中不会增加。）
	 */
	fc_state->memtupsize = fc_state->nOutputTapes;
	fc_state->memtuples = (SortTuple *) MemoryContextAlloc(fc_state->maincontext,
														fc_state->nOutputTapes * sizeof(SortTuple));
	USEMEM(fc_state, GetMemoryChunkSpace(fc_state->memtuples));

	/*
	 * 在所有输入带之间使用我们所有可用的剩余内存作为带缓冲区。在每次合并开始时，我们将把这块内存在当前传递中的输入带和输出带之间进行分配。
	 */
	fc_state->tape_buffer_mem = fc_state->availMem;
	USEMEM(fc_state, fc_state->tape_buffer_mem);
#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG, "worker %d using %zu KB of memory for tape buffers",
			 fc_state->worker, fc_state->tape_buffer_mem / 1024);
#endif

	for (;;)
	{
		/*
		 * 在第一次迭代，或者如果我们在多次合并中已读取所有输入带的运行时，是时候开始一个新过程了。将所有输出带重绕，并将它们设置为下一个过程的输入。
		 */
		if (fc_state->nInputRuns == 0)
		{
			int64		fc_input_buffer_size;

			/* 关闭旧的、已清空的输入带 */
			if (fc_state->nInputTapes > 0)
			{
				for (fc_tapenum = 0; fc_tapenum < fc_state->nInputTapes; fc_tapenum++)
					LogicalTapeClose(fc_state->inputTapes[fc_tapenum]);
				pfree(fc_state->inputTapes);
			}

			/* 上一轮的输出变为下一轮的输入。 */
			fc_state->inputTapes = fc_state->outputTapes;
			fc_state->nInputTapes = fc_state->nOutputTapes;
			fc_state->nInputRuns = fc_state->nOutputRuns;

			/*
			 * 重置输出带变量。实际的 LogicalTapes 将根据需要创建，这里我们只分配一个数组来保存它们。
			 */
			fc_state->outputTapes = palloc0(fc_state->nInputTapes * sizeof(LogicalTape *));
			fc_state->nOutputTapes = 0;
			fc_state->nOutputRuns = 0;

			/*
			 * 重新分配为带磁带缓冲区分配的内存，分配给新的输入和输出磁带。
			 */
			fc_input_buffer_size = fc_merge_read_buffer_size(fc_state->tape_buffer_mem,
													   fc_state->nInputTapes,
													   fc_state->nInputRuns,
													   fc_state->maxTapes);

#ifdef TRACE_SORT
			if (trace_sort)
				elog(LOG, "starting merge pass of %d input runs on %d tapes, " INT64_FORMAT " KB of memory for each input tape: %s",
					 fc_state->nInputRuns, fc_state->nInputTapes, fc_input_buffer_size / 1024,
					 pg_rusage_show(&fc_state->ru_start));
#endif

			/* 为归并过程准备新的输入磁带。 */
			for (fc_tapenum = 0; fc_tapenum < fc_state->nInputTapes; fc_tapenum++)
				LogicalTapeRewindForRead(fc_state->inputTapes[fc_tapenum], fc_input_buffer_size);

			/*
			 * 如果每个输入磁带上只剩一个运行，则只剩一个归并过程。 如果我们不必生成一个物化的已排序磁带，我们可以在此时停止，并现场进行最终归并。
			 */
			if ((fc_state->sortopt & TUPLESORT_RANDOMACCESS) == 0
				&& fc_state->nInputRuns <= fc_state->nInputTapes
				&& !WORKER(fc_state))
			{
				/* 告诉 logtape.c 我们不再写入 */
				LogicalTapeSetForgetFreeSpace(fc_state->tapeset);
				/* 为最终归并过程初始化 */
				fc_beginmerge(fc_state);
				fc_state->status = TSS_FINALMERGE;
				return;
			}
		}

		/* 选择一个输出磁带 */
		fc_selectnewtape(fc_state);

		/* 从每个输入磁带归并一个运行。 */
		fc_mergeonerun(fc_state);

		/*
		 * 如果输入磁带为空，并且我们仅输出一个输出运行，
		 * 我们完成了。 当前输出磁带包含最终结果。
		 */
		if (fc_state->nInputRuns == 0 && fc_state->nOutputRuns <= 1)
			break;
	}

	/*
	 * 完成。 结果在一个磁带上的单个运行中。
	 */
	fc_state->result_tape = fc_state->outputTapes[0];
	if (!WORKER(fc_state))
		LogicalTapeFreeze(fc_state->result_tape, NULL);
	else
		fc_worker_freeze_result_tape(fc_state);
	fc_state->status = TSS_SORTEDONTAPE;

	/* 关闭所有现在为空的输入磁带，以释放它们的读取缓冲区。 */
	for (fc_tapenum = 0; fc_tapenum < fc_state->nInputTapes; fc_tapenum++)
		LogicalTapeClose(fc_state->inputTapes[fc_tapenum]);
}

/*
 * 从每个输入磁带归并一个运行。
 */
static void fc_mergeonerun(Tuplesortstate *fc_state)
{
	int			fc_srcTapeIndex;
	LogicalTape *fc_srcTape;

	/*
	 * 通过将每个活动源磁带的一个元组加载到堆中来开始归并。
	 */
	fc_beginmerge(fc_state);

	/*
	 * 通过重复提取堆中最低的元组、写出它并用来自同一磁带的下一个元组（如果还有另一个）替换它来执行归并。
	 */
	while (fc_state->memtupcount > 0)
	{
		SortTuple	fc_stup;

		/* 将元组写入 destTape */
		fc_srcTapeIndex = fc_state->memtuples[0].srctape;
		fc_srcTape = fc_state->inputTapes[fc_srcTapeIndex];
		WRITETUP(fc_state, fc_state->destTape, &fc_state->memtuples[0]);

		/* 回收我们刚写出的元组的插槽，以便进行下一次读取 */
		if (fc_state->memtuples[0].tuple)
			RELEASE_SLAB_SLOT(fc_state, fc_state->memtuples[0].tuple);

		/*
		 * 从磁带中提取下一个元组，并用它替换堆中写出的元组。
		 */
		if (fc_mergereadnext(fc_state, fc_srcTape, &fc_stup))
		{
			fc_stup.srctape = fc_srcTapeIndex;
			fc_tuplesort_heap_replace_top(fc_state, &fc_stup);
		}
		else
		{
			fc_tuplesort_heap_delete_top(fc_state);
			fc_state->nInputRuns--;
		}
	}

	/*
	 * 当堆清空时，我们完成了。 在输出磁带上写入结束运行标记。
	 */
	fc_markrunend(fc_state->destTape);
}

/*
 * beginmerge - 为归并过程初始化
 *
 * 用每个输入磁带的第一个元组填充归并堆。
 */
static void fc_beginmerge(Tuplesortstate *fc_state)
{
	int			fc_activeTapes;
	int			fc_srcTapeIndex;

	/* 堆此时应该是空的 */
	Assert(fc_state->memtupcount == 0);

	fc_activeTapes = Min(fc_state->nInputTapes, fc_state->nInputRuns);

	for (fc_srcTapeIndex = 0; fc_srcTapeIndex < fc_activeTapes; fc_srcTapeIndex++)
	{
		SortTuple	fc_tup;

		if (fc_mergereadnext(fc_state, fc_state->inputTapes[fc_srcTapeIndex], &fc_tup))
		{
			fc_tup.srctape = fc_srcTapeIndex;
			fc_tuplesort_heap_insert(fc_state, &fc_tup);
		}
	}
}

/*
 * mergereadnext - 从一个合并输入磁带读取下一个元组
 *
 * 在EOF时返回false。
 */
static bool fc_mergereadnext(Tuplesortstate *fc_state, LogicalTape *fc_srcTape, SortTuple *fc_stup)
{
	unsigned int fc_tuplen;

	/* 读取下一个元组，如果有的话 */
	if ((fc_tuplen = fc_getlen(fc_srcTape, true)) == 0)
		return false;
	READTUP(fc_state, fc_stup, fc_srcTape, fc_tuplen);

	return true;
}

/*
 * dumptuples - 从 memtuples 中移除元组并将初始运行写入磁带
 *
 * 当 alltuples = true 时，转储当前内存中的所有内容。 （这个情况仅在输入数据结束时使用。）
 */
static void fc_dumptuples(Tuplesortstate *fc_state, bool fc_alltuples)
{
	int			fc_memtupwrite;
	int			fc_i;

	/*
	 * 如果我们仍然适合可用内存并且有数组插槽， 
	 * 这时没有什么可做的，除非这是在初始运行生成期间的最终调用。
	 */
	if (fc_state->memtupcount < fc_state->memtupsize && !LACKMEM(fc_state) &&
		!fc_alltuples)
		return;

	/*
	 * 在极少数情况下，最终调用可能不需要排序，因为我们刚好在输入耗尽之前的点 
	 * 恰好有所有剩余元组加载到内存中。 一般来说，短的最终运行是相当可能的，但避免创建完全空的运行。
	 * 不过，在工作线程中，我们必须生成至少一个磁带，即使它是空的。
	 */
	if (fc_state->memtupcount == 0 && fc_state->currentRun > 0)
		return;

	Assert(fc_state->status == TSS_BUILDRUNS);

	/*
	 * 似乎不太可能超出这个限制，但请不要冒险。
	 */
	if (fc_state->currentRun == INT_MAX)
		ereport(ERROR,
				(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
				 errmsg("cannot have more than %d runs for an external sort",
						INT_MAX)));

	if (fc_state->currentRun > 0)
		fc_selectnewtape(fc_state);

	fc_state->currentRun++;

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG, "worker %d starting quicksort of run %d: %s",
			 fc_state->worker, fc_state->currentRun,
			 pg_rusage_show(&fc_state->ru_start));
#endif

	/*
	 * 使用快速排序对在此运行的允许内存中积累的所有元组进行排序
	 */
	fc_tuplesort_sort_memtuples(fc_state);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG, "worker %d finished quicksort of run %d: %s",
			 fc_state->worker, fc_state->currentRun,
			 pg_rusage_show(&fc_state->ru_start));
#endif

	fc_memtupwrite = fc_state->memtupcount;
	for (fc_i = 0; fc_i < fc_memtupwrite; fc_i++)
	{
		WRITETUP(fc_state, fc_state->destTape, &fc_state->memtuples[fc_i]);
		fc_state->memtupcount--;
	}

	/*
	 * 重置元组内存。我们已经释放了之前分配的所有元组。
	 * 避免碎片化在输入元组大小发生明显变化时非常重要。
	 * 由于AllocSetFree按大小类别进行分组导致的碎片化，
	 * 如果没有采取此步骤，可能会特别糟糕。
	 */
	MemoryContextReset(fc_state->tuplecontext);

	fc_markrunend(fc_state->destTape);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG, "worker %d finished writing run %d to tape %d: %s",
			 fc_state->worker, fc_state->currentRun, (fc_state->currentRun - 1) % fc_state->nOutputTapes + 1,
			 pg_rusage_show(&fc_state->ru_start));
#endif
}

/*
 * tuplesort_rescan		- 回退并重新扫描
 */
void tuplesort_rescan(Tuplesortstate *fc_state)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

	Assert(fc_state->sortopt & TUPLESORT_RANDOMACCESS);

	switch (fc_state->status)
	{
		case TSS_SORTEDINMEM:
			fc_state->current = 0;
			fc_state->eof_reached = false;
			fc_state->markpos_offset = 0;
			fc_state->markpos_eof = false;
			break;
		case TSS_SORTEDONTAPE:
			LogicalTapeRewindForRead(fc_state->result_tape, 0);
			fc_state->eof_reached = false;
			fc_state->markpos_block = 0L;
			fc_state->markpos_offset = 0;
			fc_state->markpos_eof = false;
			break;
		default:
			elog(ERROR, "invalid tuplesort state");
			break;
	}

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * tuplesort_markpos	- 在合并排序文件中保存当前位置
 */
void tuplesort_markpos(Tuplesortstate *fc_state)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

	Assert(fc_state->sortopt & TUPLESORT_RANDOMACCESS);

	switch (fc_state->status)
	{
		case TSS_SORTEDINMEM:
			fc_state->markpos_offset = fc_state->current;
			fc_state->markpos_eof = fc_state->eof_reached;
			break;
		case TSS_SORTEDONTAPE:
			LogicalTapeTell(fc_state->result_tape,
							&fc_state->markpos_block,
							&fc_state->markpos_offset);
			fc_state->markpos_eof = fc_state->eof_reached;
			break;
		default:
			elog(ERROR, "invalid tuplesort state");
			break;
	}

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * tuplesort_restorepos - 将合并排序文件中的当前位置恢复到
 *						  上次保存的位置
 */
void tuplesort_restorepos(Tuplesortstate *fc_state)
{
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->sortcontext);

	Assert(fc_state->sortopt & TUPLESORT_RANDOMACCESS);

	switch (fc_state->status)
	{
		case TSS_SORTEDINMEM:
			fc_state->current = fc_state->markpos_offset;
			fc_state->eof_reached = fc_state->markpos_eof;
			break;
		case TSS_SORTEDONTAPE:
			LogicalTapeSeek(fc_state->result_tape,
							fc_state->markpos_block,
							fc_state->markpos_offset);
			fc_state->eof_reached = fc_state->markpos_eof;
			break;
		default:
			elog(ERROR, "invalid tuplesort state");
			break;
	}

	MemoryContextSwitchTo(fc_oldcontext);
}

/*
 * tuplesort_get_stats - 提取摘要统计信息
 *
 * 这可以在tuplesort_performsort()完成后调用，以获取
 * 有关排序如何执行的可打印摘要信息。
 */
void tuplesort_get_stats(Tuplesortstate *fc_state,
					TuplesortInstrumentation *fc_stats)
{
	/*
	 * 注意：在基于磁盘的排序中，似乎应该提供内存和磁盘使用情况。
	 * 然而，当前代码在开始将元组返回给调用者后并未准确追踪内存空间
	 * （因为我们没有考虑调用者预计要做的pfree），因此我们不能
	 * 在磁盘排序中依赖availMem。修复这个似乎不值得。
	 * 是否值得为内存上下文代码创建一个API，以告诉我们在sortcontext中
	 * 实际使用了多少？
	 */
	fc_tuplesort_updatemax(fc_state);

	if (fc_state->isMaxSpaceDisk)
		fc_stats->spaceType = SORT_SPACE_TYPE_DISK;
	else
		fc_stats->spaceType = SORT_SPACE_TYPE_MEMORY;
	fc_stats->spaceUsed = (fc_state->maxSpace + 1023) / 1024;

	switch (fc_state->maxSpaceStatus)
	{
		case TSS_SORTEDINMEM:
			if (fc_state->boundUsed)
				fc_stats->sortMethod = SORT_TYPE_TOP_N_HEAPSORT;
			else
				fc_stats->sortMethod = SORT_TYPE_QUICKSORT;
			break;
		case TSS_SORTEDONTAPE:
			fc_stats->sortMethod = SORT_TYPE_EXTERNAL_SORT;
			break;
		case TSS_FINALMERGE:
			fc_stats->sortMethod = SORT_TYPE_EXTERNAL_MERGE;
			break;
		default:
			fc_stats->sortMethod = SORT_TYPE_STILL_IN_PROGRESS;
			break;
	}
}

/*
 * 将TuplesortMethod转换为字符串。
 */
const char * tuplesort_method_name(TuplesortMethod fc_m)
{
	switch (fc_m)
	{
		case SORT_TYPE_STILL_IN_PROGRESS:
			return "still in progress";
		case SORT_TYPE_TOP_N_HEAPSORT:
			return "top-N heapsort";
		case SORT_TYPE_QUICKSORT:
			return "quicksort";
		case SORT_TYPE_EXTERNAL_SORT:
			return "external sort";
		case SORT_TYPE_EXTERNAL_MERGE:
			return "external merge";
	}

	return "unknown";
}

/*
 * 将TuplesortSpaceType转换为字符串。
 */
const char * tuplesort_space_type_name(TuplesortSpaceType fc_t)
{
	Assert(fc_t == SORT_SPACE_TYPE_DISK || fc_t == SORT_SPACE_TYPE_MEMORY);
	return fc_t == SORT_SPACE_TYPE_DISK ? "Disk" : "Memory";
}


/*
 * 根据Knuth的算法5.2.3H进行堆操作例程。
 */

/*
 * 将现有的无序SortTuples数组转换为有界堆，
 * 丢弃除了最小的“state->bound”元组之外的所有元组。
 *
 * 在处理有界堆时，我们希望将最大条目保持在根部
 * （数组条目零），而不是像正常排序情况下那样保持最小条目。
 * 这使我们能够廉价地丢弃最大条目。
 * 因此，我们暂时反转排序方向。
 */
static void fc_make_bounded_heap(Tuplesortstate *fc_state)
{
	int			fc_tupcount = fc_state->memtupcount;
	int			fc_i;

	Assert(fc_state->status == TSS_INITIAL);
	Assert(fc_state->bounded);
	Assert(fc_tupcount >= fc_state->bound);
	Assert(SERIAL(fc_state));

	/* 反转排序方向，以便最大的条目位于根部 */
	fc_reversedirection(fc_state);

	fc_state->memtupcount = 0;		/* 使堆为空 */
	for (fc_i = 0; fc_i < fc_tupcount; fc_i++)
	{
		if (fc_state->memtupcount < fc_state->bound)
		{
			/* 将下一个元组插入堆中 */
			/* 必须复制源元组以避免可能的覆盖 */
			SortTuple	fc_stup = fc_state->memtuples[fc_i];

			fc_tuplesort_heap_insert(fc_state, &fc_stup);
		}
		else
		{
			/*
			 * 堆已满。用新元组替换最大条目，或者如果它比堆中现有的任何条目都大，
			 * 则直接丢弃它。
			 */
			if (COMPARETUP(fc_state, &fc_state->memtuples[fc_i], &fc_state->memtuples[0]) <= 0)
			{
				fc_free_sort_tuple(fc_state, &fc_state->memtuples[fc_i]);
				CHECK_FOR_INTERRUPTS();
			}
			else
				fc_tuplesort_heap_replace_top(fc_state, &fc_state->memtuples[fc_i]);
		}
	}

	Assert(fc_state->memtupcount == fc_state->bound);
	fc_state->status = TSS_BOUNDED;
}

/*
 * 将有界堆转换为正确排序的数组
 */
static void fc_sort_bounded_heap(Tuplesortstate *fc_state)
{
	int			fc_tupcount = fc_state->memtupcount;

	Assert(fc_state->status == TSS_BOUNDED);
	Assert(fc_state->bounded);
	Assert(fc_tupcount == fc_state->bound);
	Assert(SERIAL(fc_state));

	/*
	 * 我们可以就地反堆化，因为每个delete-top调用将删除最大条目，
	 * 我们可以将其立即存储在末尾新释放的插槽中。
	 * 一旦我们降到单条目堆，我们就完成了。
	 */
	while (fc_state->memtupcount > 1)
	{
		SortTuple	fc_stup = fc_state->memtuples[0];

		/* 这将向上筛选下一个最大条目并减少memtupcount */
		fc_tuplesort_heap_delete_top(fc_state);
		fc_state->memtuples[fc_state->memtupcount] = fc_stup;
	}
	fc_state->memtupcount = fc_tupcount;

	/*
	 * 将排序方向反转回原始状态。这其实不是
	 * 必要的，但对于整洁来说似乎是个好主意。
	 */
	fc_reversedirection(fc_state);

	fc_state->status = TSS_SORTEDINMEM;
	fc_state->boundUsed = true;
}

/*
 * 使用特定的qsort()例程对所有内存元组进行排序。
 *
 * 当进行小型内存排序和外部排序运行时，使用快速排序。
 */
static void fc_tuplesort_sort_memtuples(Tuplesortstate *fc_state)
{
	Assert(!LEADER(fc_state));

	if (fc_state->memtupcount > 1)
	{
		/*
		 * 我们是否在 datum1 中有主列的值或缩写，并且它的比较器是否有专门化？
		 */
		if (fc_state->haveDatum1 && fc_state->sortKeys)
		{
			if (fc_state->sortKeys[0].comparator == ssup_datum_unsigned_cmp)
			{
				qsort_tuple_unsigned(fc_state->memtuples,
									 fc_state->memtupcount,
									 fc_state);
				return;
			}
#if SIZEOF_DATUM >= 8
			else if (fc_state->sortKeys[0].comparator == ssup_datum_signed_cmp)
			{
				qsort_tuple_signed(fc_state->memtuples,
								   fc_state->memtupcount,
								   fc_state);
				return;
			}
#endif
			else if (fc_state->sortKeys[0].comparator == ssup_datum_int32_cmp)
			{
				qsort_tuple_int32(fc_state->memtuples,
								  fc_state->memtupcount,
								  fc_state);
				return;
			}
		}

		/* 我们可以使用单键排序功能吗？ */
		if (fc_state->onlyKey != NULL)
		{
			qsort_ssup(fc_state->memtuples, fc_state->memtupcount,
					   fc_state->onlyKey);
		}
		else
		{
			qsort_tuple(fc_state->memtuples,
						fc_state->memtupcount,
						fc_state->comparetup,
						fc_state);
		}
	}
}

/*
 * 将一个新元组插入到空的或已存在的堆中，以维护
 * 堆不变性。调用方负责确保有空间。
 *
 * 注意：对于某些调用方，元组指向超出
 * 堆末尾的 memtuples[] 项。这是安全的，只要它
 * 不位于堆末尾的紧邻位置（即，在 [memtupcount] 数组项中）——
 * 如果是这样，它可能在被移动到堆中之前被覆盖！
 */
static void fc_tuplesort_heap_insert(Tuplesortstate *fc_state, SortTuple *fc_tuple)
{
	SortTuple  *fc_memtuples;
	int			fc_j;

	fc_memtuples = fc_state->memtuples;
	Assert(fc_state->memtupcount < fc_state->memtupsize);

	CHECK_FOR_INTERRUPTS();

	/*
	 * 根据 Knuth 5.2.3 练习 16 进行新条目的向上筛选。注意 Knuth 使用的是
	 * 基于 1 的数组索引，而不是基于 0 的。
	 */
	fc_j = fc_state->memtupcount++;
	while (fc_j > 0)
	{
		int			fc_i = (fc_j - 1) >> 1;

		if (COMPARETUP(fc_state, fc_tuple, &fc_memtuples[fc_i]) >= 0)
			break;
		fc_memtuples[fc_j] = fc_memtuples[fc_i];
		fc_j = fc_i;
	}
	fc_memtuples[fc_j] = *fc_tuple;
}

/*
 * 从堆中移除 state->memtuples[0] 的元组。减少
 * memtupcount，并进行上滤以维护堆不变性。
 *
 * 调用方已经释放了顶节点指向的元组，
 * 如果必要的话。
 */
static void fc_tuplesort_heap_delete_top(Tuplesortstate *fc_state)
{
	SortTuple  *fc_memtuples = fc_state->memtuples;
	SortTuple  *fc_tuple;

	if (--fc_state->memtupcount <= 0)
		return;

	/*
	 * 移除堆中的最后一个元组，并通过用它替换
	 * 当前顶节点来重新插入。
	 */
	fc_tuple = &fc_memtuples[fc_state->memtupcount];
	fc_tuplesort_heap_replace_top(fc_state, fc_tuple);
}

/*
 * 用一个新元组替换 state->memtuples[0] 的元组。进行上滤以
 * 维护堆不变性。
 *
 * 这对应于 Knuth 的“上滤”算法（算法 5.2.3H，
 * 堆排序，步骤 H3-H8）。
 */
static void fc_tuplesort_heap_replace_top(Tuplesortstate *fc_state, SortTuple *fc_tuple)
{
	SortTuple  *fc_memtuples = fc_state->memtuples;
	unsigned int fc_i,
				fc_n;

	Assert(fc_state->memtupcount >= 1);

	CHECK_FOR_INTERRUPTS();

	/*
	 * state->memtupcount 是“int”，但我们对 i、j、n 使用“unsigned int”。
	 * 这防止在“2 * i + 1”计算时发生溢出，因为在循环顶部
	 * 我们必须有 i < n <= INT_MAX <= UINT_MAX/2。
	 */
	fc_n = fc_state->memtupcount;
	fc_i = 0;						/* i 是“洞”的位置 */
	for (;;)
	{
		unsigned int fc_j = 2 * fc_i + 1;

		if (fc_j >= fc_n)
			break;
		if (fc_j + 1 < fc_n &&
			COMPARETUP(fc_state, &fc_memtuples[fc_j], &fc_memtuples[fc_j + 1]) > 0)
			fc_j++;
		if (COMPARETUP(fc_state, fc_tuple, &fc_memtuples[fc_j]) <= 0)
			break;
		fc_memtuples[fc_i] = fc_memtuples[fc_j];
		fc_i = fc_j;
	}
	fc_memtuples[fc_i] = *fc_tuple;
}

/*
 * 函数用于从其当前状态反转排序方向
 *
 * 在执行哈希元组排序时调用此函数是不安全的
 */
static void fc_reversedirection(Tuplesortstate *fc_state)
{
	SortSupport fc_sortKey = fc_state->sortKeys;
	int			fc_nkey;

	for (fc_nkey = 0; fc_nkey < fc_state->nKeys; fc_nkey++, fc_sortKey++)
	{
		fc_sortKey->ssup_reverse = !fc_sortKey->ssup_reverse;
		fc_sortKey->ssup_nulls_first = !fc_sortKey->ssup_nulls_first;
	}
}


/*
 * 磁带接口例程
 */

static unsigned int fc_getlen(LogicalTape *fc_tape, bool fc_eofOK)
{
	unsigned int fc_len;

	if (LogicalTapeRead(fc_tape,
						&fc_len, sizeof(fc_len)) != sizeof(fc_len))
		elog(ERROR, "unexpected end of tape");
	if (fc_len == 0 && !fc_eofOK)
		elog(ERROR, "unexpected end of data");
	return fc_len;
}

static void fc_markrunend(LogicalTape *fc_tape)
{
	unsigned int fc_len = 0;

	LogicalTapeWrite(fc_tape, (void *) &fc_len, sizeof(fc_len));
}

/*
 * 从 READTUP() 例程中获取元组内存。
 *
 * 我们使用来自 slab 分配器的下一个空闲槽，或者如果元组
 * 对于此来得太大则使用 palloc()。
 */
static void * fc_readtup_alloc(Tuplesortstate *fc_state, Size fc_tuplen)
{
	SlabSlot   *fc_buf;

	/*
	 * 我们预先分配足够的槽位在 slab 区域，以确保不会
	 * 用尽空间。
	 */
	Assert(fc_state->slabFreeHead);

	if (fc_tuplen > SLAB_SLOT_SIZE || !fc_state->slabFreeHead)
		return MemoryContextAlloc(fc_state->sortcontext, fc_tuplen);
	else
	{
		fc_buf = fc_state->slabFreeHead;
		/* 重用此槽 */
		fc_state->slabFreeHead = fc_buf->nextfree;

		return fc_buf;
	}
}


/*
 * 专门针对 HeapTuple（实际上是 MinimalTuple）情况的例程
 */

static int fc_comparetup_heap(const SortTuple *fc_a, const SortTuple *fc_b, Tuplesortstate *fc_state)
{
	SortSupport fc_sortKey = fc_state->sortKeys;
	HeapTupleData fc_ltup;
	HeapTupleData fc_rtup;
	TupleDesc	fc_tupDesc;
	int			fc_nkey;
	int32		fc_compare;
	AttrNumber	fc_attno;
	Datum		fc_datum1,
				fc_datum2;
	bool		fc_isnull1,
				fc_isnull2;


	/* 比较主排序键 */
	fc_compare = ApplySortComparator(fc_a->datum1, fc_a->isnull1,
								  fc_b->datum1, fc_b->isnull1,
								  fc_sortKey);
	if (fc_compare != 0)
		return fc_compare;

	/* 比较附加排序键 */
	fc_ltup.t_len = ((MinimalTuple) fc_a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
	fc_ltup.t_data = (HeapTupleHeader) ((char *) fc_a->tuple - MINIMAL_TUPLE_OFFSET);
	fc_rtup.t_len = ((MinimalTuple) fc_b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
	fc_rtup.t_data = (HeapTupleHeader) ((char *) fc_b->tuple - MINIMAL_TUPLE_OFFSET);
	fc_tupDesc = fc_state->tupDesc;

	if (fc_sortKey->abbrev_converter)
	{
		fc_attno = fc_sortKey->ssup_attno;

		fc_datum1 = heap_getattr(&fc_ltup, fc_attno, fc_tupDesc, &fc_isnull1);
		fc_datum2 = heap_getattr(&fc_rtup, fc_attno, fc_tupDesc, &fc_isnull2);

		fc_compare = ApplySortAbbrevFullComparator(fc_datum1, fc_isnull1,
												fc_datum2, fc_isnull2,
												fc_sortKey);
		if (fc_compare != 0)
			return fc_compare;
	}

	fc_sortKey++;
	for (fc_nkey = 1; fc_nkey < fc_state->nKeys; fc_nkey++, fc_sortKey++)
	{
		fc_attno = fc_sortKey->ssup_attno;

		fc_datum1 = heap_getattr(&fc_ltup, fc_attno, fc_tupDesc, &fc_isnull1);
		fc_datum2 = heap_getattr(&fc_rtup, fc_attno, fc_tupDesc, &fc_isnull2);

		fc_compare = ApplySortComparator(fc_datum1, fc_isnull1,
									  fc_datum2, fc_isnull2,
									  fc_sortKey);
		if (fc_compare != 0)
			return fc_compare;
	}

	return 0;
}

static void fc_copytup_heap(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup)
{
	/*
	 * 我们预期传入的“tup”是 TupleTableSlot，并使用
	 * 导出的接口形成一个 MinimalTuple。
	 */
	TupleTableSlot *fc_slot = (TupleTableSlot *) fc_tup;
	Datum		fc_original;
	MinimalTuple fc_tuple;
	HeapTupleData fc_htup;
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->tuplecontext);

	/* 将元组复制到排序存储中 */
	fc_tuple = ExecCopySlotMinimalTuple(fc_slot);
	fc_stup->tuple = (void *) fc_tuple;
	USEMEM(fc_state, GetMemoryChunkSpace(fc_tuple));
	/* 设置第一列键值 */
	fc_htup.t_len = fc_tuple->t_len + MINIMAL_TUPLE_OFFSET;
	fc_htup.t_data = (HeapTupleHeader) ((char *) fc_tuple - MINIMAL_TUPLE_OFFSET);
	fc_original = heap_getattr(&fc_htup,
							fc_state->sortKeys[0].ssup_attno,
							fc_state->tupDesc,
							&fc_stup->isnull1);

	MemoryContextSwitchTo(fc_oldcontext);

	if (!fc_state->sortKeys->abbrev_converter || fc_stup->isnull1)
	{
		/*
		 * 存储普通 Datum 表示，或 NULL 值。如果存在一个
		 * 转换器，它不会期望 NULL 值，且成本模型不
		 * 需要考虑 NULL，因此在这种情况下我们避免调用
		 * 转换器，并将 datum1 设置为零表示（为了保持一致
		 * 并支持对 NULL 缩略键的便宜不等式测试）。
		 */
		fc_stup->datum1 = fc_original;
	}
	else if (!fc_consider_abort_common(fc_state))
	{
		/* 存储缩略键表示 */
		fc_stup->datum1 = fc_state->sortKeys->abbrev_converter(fc_original,
														 fc_state->sortKeys);
	}
	else
	{
		/* 中止缩略处理 */
		int			fc_i;

		fc_stup->datum1 = fc_original;

		/*
		 * 将状态设置为一致，以确保永远不会尝试缩略。
		 *
		 * 在已经复制的元组中更改 datum1 表示，以确保
		 * 一致的表示（当前元组刚刚处理）。如果某些转储的元组
		 * 已经在磁带上排序也没有关系，因为序列化的元组缺少
		 * 缩略键（TSS_BUILDRUNS 状态无论如何都会防止控制
		 * 达到这里）。
		 */
		for (fc_i = 0; fc_i < fc_state->memtupcount; fc_i++)
		{
			SortTuple  *fc_mtup = &fc_state->memtuples[fc_i];

			fc_htup.t_len = ((MinimalTuple) fc_mtup->tuple)->t_len +
				MINIMAL_TUPLE_OFFSET;
			fc_htup.t_data = (HeapTupleHeader) ((char *) fc_mtup->tuple -
											 MINIMAL_TUPLE_OFFSET);

			fc_mtup->datum1 = heap_getattr(&fc_htup,
										fc_state->sortKeys[0].ssup_attno,
										fc_state->tupDesc,
										&fc_mtup->isnull1);
		}
	}
}

static void fc_writetup_heap(Tuplesortstate *fc_state, LogicalTape *fc_tape, SortTuple *fc_stup)
{
	MinimalTuple fc_tuple = (MinimalTuple) fc_stup->tuple;

	/* 我们将要写入的MinimalTuple部分： */
	char	   *fc_tupbody = (char *) fc_tuple + MINIMAL_TUPLE_DATA_OFFSET;
	unsigned int fc_tupbodylen = fc_tuple->t_len - MINIMAL_TUPLE_DATA_OFFSET;

	/* 磁盘上的总占用空间： */
	unsigned int fc_tuplen = fc_tupbodylen + sizeof(int);

	LogicalTapeWrite(fc_tape, (void *) &fc_tuplen, sizeof(fc_tuplen));
	LogicalTapeWrite(fc_tape, (void *) fc_tupbody, fc_tupbodylen);
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeWrite(fc_tape, (void *) &fc_tuplen, sizeof(fc_tuplen));

	if (!fc_state->slabAllocatorUsed)
	{
		FREEMEM(fc_state, GetMemoryChunkSpace(fc_tuple));
		heap_free_minimal_tuple(fc_tuple);
	}
}

static void fc_readtup_heap(Tuplesortstate *fc_state, SortTuple *fc_stup,
			 LogicalTape *fc_tape, unsigned int fc_len)
{
	unsigned int fc_tupbodylen = fc_len - sizeof(int);
	unsigned int fc_tuplen = fc_tupbodylen + MINIMAL_TUPLE_DATA_OFFSET;
	MinimalTuple fc_tuple = (MinimalTuple) fc_readtup_alloc(fc_state, fc_tuplen);
	char	   *fc_tupbody = (char *) fc_tuple + MINIMAL_TUPLE_DATA_OFFSET;
	HeapTupleData fc_htup;

	/* 读取元组主体 */
	fc_tuple->t_len = fc_tuplen;
	LogicalTapeReadExact(fc_tape, fc_tupbody, fc_tupbodylen);
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeReadExact(fc_tape, &fc_tuplen, sizeof(fc_tuplen));
	fc_stup->tuple = (void *) fc_tuple;
	/* 设置第一列键值 */
	fc_htup.t_len = fc_tuple->t_len + MINIMAL_TUPLE_OFFSET;
	fc_htup.t_data = (HeapTupleHeader) ((char *) fc_tuple - MINIMAL_TUPLE_OFFSET);
	fc_stup->datum1 = heap_getattr(&fc_htup,
								fc_state->sortKeys[0].ssup_attno,
								fc_state->tupDesc,
								&fc_stup->isnull1);
}

/*
 * 针对CLUSTER情况的专用例程（堆元组数据，符合btree索引定义的比较）
 */

static int fc_comparetup_cluster(const SortTuple *fc_a, const SortTuple *fc_b,
				   Tuplesortstate *fc_state)
{
	SortSupport fc_sortKey = fc_state->sortKeys;
	HeapTuple	fc_ltup;
	HeapTuple	fc_rtup;
	TupleDesc	fc_tupDesc;
	int			fc_nkey;
	int32		fc_compare;
	Datum		fc_datum1,
				fc_datum2;
	bool		fc_isnull1,
				fc_isnull2;

	/* 准备比较额外的排序键 */
	fc_ltup = (HeapTuple) fc_a->tuple;
	fc_rtup = (HeapTuple) fc_b->tuple;
	fc_tupDesc = fc_state->tupDesc;

	/* 如果主要排序键简单，则比较主要排序键 */
	if (fc_state->haveDatum1)
	{
		fc_compare = ApplySortComparator(fc_a->datum1, fc_a->isnull1,
									  fc_b->datum1, fc_b->isnull1,
									  fc_sortKey);
		if (fc_compare != 0)
			return fc_compare;

		if (fc_sortKey->abbrev_converter)
		{
			AttrNumber	fc_leading = fc_state->indexInfo->ii_IndexAttrNumbers[0];

			fc_datum1 = heap_getattr(fc_ltup, fc_leading, fc_tupDesc, &fc_isnull1);
			fc_datum2 = heap_getattr(fc_rtup, fc_leading, fc_tupDesc, &fc_isnull2);

			fc_compare = ApplySortAbbrevFullComparator(fc_datum1, fc_isnull1,
													fc_datum2, fc_isnull2,
													fc_sortKey);
		}
		if (fc_compare != 0 || fc_state->nKeys == 1)
			return fc_compare;
		/* 以困难的方式比较额外的列 */
		fc_sortKey++;
		fc_nkey = 1;
	}
	else
	{
		/* 必须以困难的方式比较所有键 */
		fc_nkey = 0;
	}

	if (fc_state->indexInfo->ii_Expressions == NULL)
	{
		/* 如果不是表达式索引，则仅比较适当的堆属性 */

		for (; fc_nkey < fc_state->nKeys; fc_nkey++, fc_sortKey++)
		{
			AttrNumber	fc_attno = fc_state->indexInfo->ii_IndexAttrNumbers[fc_nkey];

			fc_datum1 = heap_getattr(fc_ltup, fc_attno, fc_tupDesc, &fc_isnull1);
			fc_datum2 = heap_getattr(fc_rtup, fc_attno, fc_tupDesc, &fc_isnull2);

			fc_compare = ApplySortComparator(fc_datum1, fc_isnull1,
										  fc_datum2, fc_isnull2,
										  fc_sortKey);
			if (fc_compare != 0)
				return fc_compare;
		}
	}
	else
	{
		/*
		 * 在表达式索引情况下，计算整个索引元组
		 * 然后比较值。也许只计算我们需要比较的列会更快，但这将要求
		 * 复制FormIndexDatum中的所有逻辑。
		 */
		Datum		fc_l_index_values[INDEX_MAX_KEYS];
		bool		fc_l_index_isnull[INDEX_MAX_KEYS];
		Datum		fc_r_index_values[INDEX_MAX_KEYS];
		bool		fc_r_index_isnull[INDEX_MAX_KEYS];
		TupleTableSlot *fc_ecxt_scantuple;

		/* 每次重置上下文以防止内存泄漏 */
		ResetPerTupleExprContext(fc_state->estate);

		fc_ecxt_scantuple = GetPerTupleExprContext(fc_state->estate)->ecxt_scantuple;

		ExecStoreHeapTuple(fc_ltup, fc_ecxt_scantuple, false);
		FormIndexDatum(fc_state->indexInfo, fc_ecxt_scantuple, fc_state->estate,
					   fc_l_index_values, fc_l_index_isnull);

		ExecStoreHeapTuple(fc_rtup, fc_ecxt_scantuple, false);
		FormIndexDatum(fc_state->indexInfo, fc_ecxt_scantuple, fc_state->estate,
					   fc_r_index_values, fc_r_index_isnull);

		for (; fc_nkey < fc_state->nKeys; fc_nkey++, fc_sortKey++)
		{
			fc_compare = ApplySortComparator(fc_l_index_values[fc_nkey],
										  fc_l_index_isnull[fc_nkey],
										  fc_r_index_values[fc_nkey],
										  fc_r_index_isnull[fc_nkey],
										  fc_sortKey);
			if (fc_compare != 0)
				return fc_compare;
		}
	}

	return 0;
}

static void fc_copytup_cluster(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup)
{
	HeapTuple	fc_tuple = (HeapTuple) fc_tup;
	Datum		fc_original;
	MemoryContext fc_oldcontext = MemoryContextSwitchTo(fc_state->tuplecontext);

	/* 将元组复制到排序存储中 */
	fc_tuple = heap_copytuple(fc_tuple);
	fc_stup->tuple = (void *) fc_tuple;
	USEMEM(fc_state, GetMemoryChunkSpace(fc_tuple));

	MemoryContextSwitchTo(fc_oldcontext);

	/*
	 * 设置第一列键值，并在可能的情况下缩写，如果是简单列
	 */
	if (!fc_state->haveDatum1)
		return;

	fc_original = heap_getattr(fc_tuple,
							fc_state->indexInfo->ii_IndexAttrNumbers[0],
							fc_state->tupDesc,
							&fc_stup->isnull1);

	if (!fc_state->sortKeys->abbrev_converter || fc_stup->isnull1)
	{
		/*
		 * 存储普通 Datum 表示，或 NULL 值。如果存在一个
		 * 转换器，它不会期望 NULL 值，且成本模型不
		 * 需要考虑 NULL，因此在这种情况下我们避免调用
		 * 转换器，并将 datum1 设置为零表示（为了保持一致
		 * 并支持对 NULL 缩略键的便宜不等式测试）。
		 */
		fc_stup->datum1 = fc_original;
	}
	else if (!fc_consider_abort_common(fc_state))
	{
		/* 存储缩略键表示 */
		fc_stup->datum1 = fc_state->sortKeys->abbrev_converter(fc_original,
														 fc_state->sortKeys);
	}
	else
	{
		/* 中止缩略处理 */
		int			fc_i;

		fc_stup->datum1 = fc_original;

		/*
		 * 将状态设置为一致，以确保永远不会尝试缩略。
		 *
		 * 在已经复制的元组中更改 datum1 表示，以确保
		 * 一致的表示（当前元组刚刚处理）。如果某些转储的元组
		 * 已经在磁带上排序也没有关系，因为序列化的元组缺少
		 * 缩略键（TSS_BUILDRUNS 状态无论如何都会防止控制
		 * 达到这里）。
		 */
		for (fc_i = 0; fc_i < fc_state->memtupcount; fc_i++)
		{
			SortTuple  *fc_mtup = &fc_state->memtuples[fc_i];

			fc_tuple = (HeapTuple) fc_mtup->tuple;
			fc_mtup->datum1 = heap_getattr(fc_tuple,
										fc_state->indexInfo->ii_IndexAttrNumbers[0],
										fc_state->tupDesc,
										&fc_mtup->isnull1);
		}
	}
}

static void fc_writetup_cluster(Tuplesortstate *fc_state, LogicalTape *fc_tape, SortTuple *fc_stup)
{
	HeapTuple	fc_tuple = (HeapTuple) fc_stup->tuple;
	unsigned int fc_tuplen = fc_tuple->t_len + sizeof(ItemPointerData) + sizeof(int);

	/* 我们需要存储t_self，但不需要HeapTupleData的其他字段 */
	LogicalTapeWrite(fc_tape, &fc_tuplen, sizeof(fc_tuplen));
	LogicalTapeWrite(fc_tape, &fc_tuple->t_self, sizeof(ItemPointerData));
	LogicalTapeWrite(fc_tape, fc_tuple->t_data, fc_tuple->t_len);
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeWrite(fc_tape, &fc_tuplen, sizeof(fc_tuplen));

	if (!fc_state->slabAllocatorUsed)
	{
		FREEMEM(fc_state, GetMemoryChunkSpace(fc_tuple));
		heap_freetuple(fc_tuple);
	}
}

static void fc_readtup_cluster(Tuplesortstate *fc_state, SortTuple *fc_stup,
				LogicalTape *fc_tape, unsigned int fc_tuplen)
{
	unsigned int fc_t_len = fc_tuplen - sizeof(ItemPointerData) - sizeof(int);
	HeapTuple	fc_tuple = (HeapTuple) fc_readtup_alloc(fc_state,
												  fc_t_len + HEAPTUPLESIZE);

	/* 重新构建HeapTupleData头 */
	fc_tuple->t_data = (HeapTupleHeader) ((char *) fc_tuple + HEAPTUPLESIZE);
	fc_tuple->t_len = fc_t_len;
	LogicalTapeReadExact(fc_tape, &fc_tuple->t_self, sizeof(ItemPointerData));
	/* 我们目前不打算重新构建t_tableOid */
	fc_tuple->t_tableOid = InvalidOid;
	/* 读取元组主体 */
	LogicalTapeReadExact(fc_tape, fc_tuple->t_data, fc_tuple->t_len);
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeReadExact(fc_tape, &fc_tuplen, sizeof(fc_tuplen));
	fc_stup->tuple = (void *) fc_tuple;
	/* 设置第一列键值，如果是简单列 */
	if (fc_state->haveDatum1)
		fc_stup->datum1 = heap_getattr(fc_tuple,
									fc_state->indexInfo->ii_IndexAttrNumbers[0],
									fc_state->tupDesc,
									&fc_stup->isnull1);
}

/*
 * 专门为 IndexTuple 情况设计的程序
 *
 * btree 和 hash 情况需要单独的比较函数，但 IndexTuple 的表示形式是相同的，因此复制/写入/读取支持函数可以共享。
 */

static int fc_comparetup_index_btree(const SortTuple *fc_a, const SortTuple *fc_b,
					   Tuplesortstate *fc_state)
{
	/*
	 * 这与 comparetup_heap() 类似，但期望索引元组。还有对唯一性的特殊处理，以及对相等键在最后的特殊处理。
	 */
	SortSupport fc_sortKey = fc_state->sortKeys;
	IndexTuple	fc_tuple1;
	IndexTuple	fc_tuple2;
	int			fc_keysz;
	TupleDesc	fc_tupDes;
	bool		fc_equal_hasnull = false;
	int			fc_nkey;
	int32		fc_compare;
	Datum		fc_datum1,
				fc_datum2;
	bool		fc_isnull1,
				fc_isnull2;


	/* 比较主排序键 */
	fc_compare = ApplySortComparator(fc_a->datum1, fc_a->isnull1,
								  fc_b->datum1, fc_b->isnull1,
								  fc_sortKey);
	if (fc_compare != 0)
		return fc_compare;

	/* 比较附加排序键 */
	fc_tuple1 = (IndexTuple) fc_a->tuple;
	fc_tuple2 = (IndexTuple) fc_b->tuple;
	fc_keysz = fc_state->nKeys;
	fc_tupDes = RelationGetDescr(fc_state->indexRel);

	if (fc_sortKey->abbrev_converter)
	{
		fc_datum1 = index_getattr(fc_tuple1, 1, fc_tupDes, &fc_isnull1);
		fc_datum2 = index_getattr(fc_tuple2, 1, fc_tupDes, &fc_isnull2);

		fc_compare = ApplySortAbbrevFullComparator(fc_datum1, fc_isnull1,
												fc_datum2, fc_isnull2,
												fc_sortKey);
		if (fc_compare != 0)
			return fc_compare;
	}

	/* 它们是相等的，因此我们只需检查一个空标志 */
	if (fc_a->isnull1)
		fc_equal_hasnull = true;

	fc_sortKey++;
	for (fc_nkey = 2; fc_nkey <= fc_keysz; fc_nkey++, fc_sortKey++)
	{
		fc_datum1 = index_getattr(fc_tuple1, fc_nkey, fc_tupDes, &fc_isnull1);
		fc_datum2 = index_getattr(fc_tuple2, fc_nkey, fc_tupDes, &fc_isnull2);

		fc_compare = ApplySortComparator(fc_datum1, fc_isnull1,
									  fc_datum2, fc_isnull2,
									  fc_sortKey);
		if (fc_compare != 0)
			return fc_compare;		/* 当找到不相等的属性时完成 */

		/* 它们是相等的，因此我们只需检查一个空标志 */
		if (fc_isnull1)
			fc_equal_hasnull = true;
	}

	/*
	 * 如果 btree 要求我们强制唯一性，则在检测到两个相等的元组时提出抱怨（除非至少有一个 NULL 字段，并且 NULLS NOT DISTINCT 未被设置）。
	 *
	 * 在此进行测试是足够的，因为如果两个元组相等，它们 *必须* 在某个排序阶段进行比较——否则排序算法将不会检查一个必须出现在另一个之前。
	 */
	if (fc_state->enforceUnique && !(!fc_state->uniqueNullsNotDistinct && fc_equal_hasnull))
	{
		Datum		fc_values[INDEX_MAX_KEYS];
		bool		fc_isnull[INDEX_MAX_KEYS];
		char	   *fc_key_desc;

		/*
		 * 一些相当脑袋简单的 qsort 实现（例如 QNX 4 中的实现）有时会调用比较例程来将一个值与其自身进行比较，但我们始终使用我们自己的实现，该实现不会这样做。
		 */
		Assert(fc_tuple1 != fc_tuple2);

		index_deform_tuple(fc_tuple1, fc_tupDes, fc_values, fc_isnull);

		fc_key_desc = BuildIndexValueDescription(fc_state->indexRel, fc_values, fc_isnull);

		ereport(ERROR,
				(errcode(ERRCODE_UNIQUE_VIOLATION),
				 errmsg("could not create unique index \"%s\"",
						RelationGetRelationName(fc_state->indexRel)),
				 fc_key_desc ? errdetail("Key %s is duplicated.", fc_key_desc) :
				 errdetail("Duplicate keys exist."),
				 errtableconstraint(fc_state->heapRel,
									RelationGetRelationName(fc_state->indexRel))));
	}

	/*
	 * 如果键值相等，我们根据 ItemPointer 进行排序。这对于 btree 索引是必需的，因为堆 TID 被视为隐式最后键属性，以确保索引中的所有键在物理上都是唯一的。
	 */
	{
		BlockNumber fc_blk1 = ItemPointerGetBlockNumber(&fc_tuple1->t_tid);
		BlockNumber fc_blk2 = ItemPointerGetBlockNumber(&fc_tuple2->t_tid);

		if (fc_blk1 != fc_blk2)
			return (fc_blk1 < fc_blk2) ? -1 : 1;
	}
	{
		OffsetNumber fc_pos1 = ItemPointerGetOffsetNumber(&fc_tuple1->t_tid);
		OffsetNumber fc_pos2 = ItemPointerGetOffsetNumber(&fc_tuple2->t_tid);

		if (fc_pos1 != fc_pos2)
			return (fc_pos1 < fc_pos2) ? -1 : 1;
	}

	/* ItemPointer 值永远不应相等 */
	Assert(false);

	return 0;
}

static int fc_comparetup_index_hash(const SortTuple *fc_a, const SortTuple *fc_b,
					  Tuplesortstate *fc_state)
{
	Bucket		fc_bucket1;
	Bucket		fc_bucket2;
	IndexTuple	fc_tuple1;
	IndexTuple	fc_tuple2;

	/*
	 * 获取 hash 键并屏蔽掉我们不想排序的位。我们知道索引元组的第一列是 hash 键。
	 */
	Assert(!fc_a->isnull1);
	fc_bucket1 = _hash_hashkey2bucket(DatumGetUInt32(fc_a->datum1),
								   fc_state->max_buckets, fc_state->high_mask,
								   fc_state->low_mask);
	Assert(!fc_b->isnull1);
	fc_bucket2 = _hash_hashkey2bucket(DatumGetUInt32(fc_b->datum1),
								   fc_state->max_buckets, fc_state->high_mask,
								   fc_state->low_mask);
	if (fc_bucket1 > fc_bucket2)
		return 1;
	else if (fc_bucket1 < fc_bucket2)
		return -1;

	/*
	 * 如果 hash 值相等，我们根据 ItemPointer 进行排序。这不会影响已完成索引的有效性，但在物理顺序中进行索引扫描可能会很有用。
	 */
	fc_tuple1 = (IndexTuple) fc_a->tuple;
	fc_tuple2 = (IndexTuple) fc_b->tuple;

	{
		BlockNumber fc_blk1 = ItemPointerGetBlockNumber(&fc_tuple1->t_tid);
		BlockNumber fc_blk2 = ItemPointerGetBlockNumber(&fc_tuple2->t_tid);

		if (fc_blk1 != fc_blk2)
			return (fc_blk1 < fc_blk2) ? -1 : 1;
	}
	{
		OffsetNumber fc_pos1 = ItemPointerGetOffsetNumber(&fc_tuple1->t_tid);
		OffsetNumber fc_pos2 = ItemPointerGetOffsetNumber(&fc_tuple2->t_tid);

		if (fc_pos1 != fc_pos2)
			return (fc_pos1 < fc_pos2) ? -1 : 1;
	}

	/* ItemPointer 值永远不应相等 */
	Assert(false);

	return 0;
}

static void fc_copytup_index(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup)
{
	/* 当前不需要 */
	elog(ERROR, "copytup_index() should not be called");
}

static void fc_writetup_index(Tuplesortstate *fc_state, LogicalTape *fc_tape, SortTuple *fc_stup)
{
	IndexTuple	fc_tuple = (IndexTuple) fc_stup->tuple;
	unsigned int fc_tuplen;

	fc_tuplen = IndexTupleSize(fc_tuple) + sizeof(fc_tuplen);
	LogicalTapeWrite(fc_tape, (void *) &fc_tuplen, sizeof(fc_tuplen));
	LogicalTapeWrite(fc_tape, (void *) fc_tuple, IndexTupleSize(fc_tuple));
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeWrite(fc_tape, (void *) &fc_tuplen, sizeof(fc_tuplen));

	if (!fc_state->slabAllocatorUsed)
	{
		FREEMEM(fc_state, GetMemoryChunkSpace(fc_tuple));
		pfree(fc_tuple);
	}
}

static void fc_readtup_index(Tuplesortstate *fc_state, SortTuple *fc_stup,
			  LogicalTape *fc_tape, unsigned int fc_len)
{
	unsigned int fc_tuplen = fc_len - sizeof(unsigned int);
	IndexTuple	fc_tuple = (IndexTuple) fc_readtup_alloc(fc_state, fc_tuplen);

	LogicalTapeReadExact(fc_tape, fc_tuple, fc_tuplen);
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeReadExact(fc_tape, &fc_tuplen, sizeof(fc_tuplen));
	fc_stup->tuple = (void *) fc_tuple;
	/* 设置第一列键值 */
	fc_stup->datum1 = index_getattr(fc_tuple,
								 1,
								 RelationGetDescr(fc_state->indexRel),
								 &fc_stup->isnull1);
}

/*
 * 专门为 DatumTuple 情况设计的程序
 */

static int fc_comparetup_datum(const SortTuple *fc_a, const SortTuple *fc_b, Tuplesortstate *fc_state)
{
	int			fc_compare;

	fc_compare = ApplySortComparator(fc_a->datum1, fc_a->isnull1,
								  fc_b->datum1, fc_b->isnull1,
								  fc_state->sortKeys);
	if (fc_compare != 0)
		return fc_compare;

	/* 如果我们有缩写，则 "tuple" 具有原始值 */

	if (fc_state->sortKeys->abbrev_converter)
		fc_compare = ApplySortAbbrevFullComparator(PointerGetDatum(fc_a->tuple), fc_a->isnull1,
												PointerGetDatum(fc_b->tuple), fc_b->isnull1,
												fc_state->sortKeys);

	return fc_compare;
}

static void fc_copytup_datum(Tuplesortstate *fc_state, SortTuple *fc_stup, void *fc_tup)
{
	/* 当前不需要 */
	elog(ERROR, "copytup_datum() should not be called");
}

static void fc_writetup_datum(Tuplesortstate *fc_state, LogicalTape *fc_tape, SortTuple *fc_stup)
{
	void	   *fc_waddr;
	unsigned int fc_tuplen;
	unsigned int fc_writtenlen;

	if (fc_stup->isnull1)
	{
		fc_waddr = NULL;
		fc_tuplen = 0;
	}
	else if (!fc_state->tuples)
	{
		fc_waddr = &fc_stup->datum1;
		fc_tuplen = sizeof(Datum);
	}
	else
	{
		fc_waddr = fc_stup->tuple;
		fc_tuplen = datumGetSize(PointerGetDatum(fc_stup->tuple), false, fc_state->datumTypeLen);
		Assert(fc_tuplen != 0);
	}

	fc_writtenlen = fc_tuplen + sizeof(unsigned int);

	LogicalTapeWrite(fc_tape, (void *) &fc_writtenlen, sizeof(fc_writtenlen));
	LogicalTapeWrite(fc_tape, fc_waddr, fc_tuplen);
	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeWrite(fc_tape, (void *) &fc_writtenlen, sizeof(fc_writtenlen));

	if (!fc_state->slabAllocatorUsed && fc_stup->tuple)
	{
		FREEMEM(fc_state, GetMemoryChunkSpace(fc_stup->tuple));
		pfree(fc_stup->tuple);
	}
}

static void fc_readtup_datum(Tuplesortstate *fc_state, SortTuple *fc_stup,
			  LogicalTape *fc_tape, unsigned int fc_len)
{
	unsigned int fc_tuplen = fc_len - sizeof(unsigned int);

	if (fc_tuplen == 0)
	{
		/* 它是 NULL */
		fc_stup->datum1 = (Datum) 0;
		fc_stup->isnull1 = true;
		fc_stup->tuple = NULL;
	}
	else if (!fc_state->tuples)
	{
		Assert(fc_tuplen == sizeof(Datum));
		LogicalTapeReadExact(fc_tape, &fc_stup->datum1, fc_tuplen);
		fc_stup->isnull1 = false;
		fc_stup->tuple = NULL;
	}
	else
	{
		void	   *fc_raddr = fc_readtup_alloc(fc_state, fc_tuplen);

		LogicalTapeReadExact(fc_tape, fc_raddr, fc_tuplen);
		fc_stup->datum1 = PointerGetDatum(fc_raddr);
		fc_stup->isnull1 = false;
		fc_stup->tuple = fc_raddr;
	}

	if (fc_state->sortopt & TUPLESORT_RANDOMACCESS)	/* 需要尾随长度
													 * 字段？ */
		LogicalTapeReadExact(fc_tape, &fc_tuplen, sizeof(fc_tuplen));
}

/*
 * 并行排序程序
 */

/*
 * tuplesort_estimate_shared - 估算所需的共享内存分配
 *
 * nWorkers 是对工人数的估算（即将请求的数量）。
 */
Size tuplesort_estimate_shared(int fc_nWorkers)
{
	Size		fc_tapesSize;

	Assert(fc_nWorkers > 0);

	/* 确保 BufFile 共享状态经过 MAXALIGN 对齐 */
	fc_tapesSize = mul_size(sizeof(TapeShare), fc_nWorkers);
	fc_tapesSize = MAXALIGN(add_size(fc_tapesSize, offsetof(Sharedsort, tapes)));

	return fc_tapesSize;
}

/*
 * tuplesort_initialize_shared - 初始化共享的 tuplesort 状态
 *
 * 必须在启动工作进程之前由领导进程调用，以
 * 确立工作 tuplesortstates 所需的前置状态。 nWorkers
 * 应与传递给 tuplesort_estimate_shared() 的参数匹配。
 */
void tuplesort_initialize_shared(Sharedsort *fc_shared, int fc_nWorkers, dsm_segment *fc_seg)
{
	int			fc_i;

	Assert(fc_nWorkers > 0);

	SpinLockInit(&fc_shared->mutex);
	fc_shared->currentWorker = 0;
	fc_shared->workersFinished = 0;
	SharedFileSetInit(&fc_shared->fileset, fc_seg);
	fc_shared->nTapes = fc_nWorkers;
	for (fc_i = 0; fc_i < fc_nWorkers; fc_i++)
	{
		fc_shared->tapes[fc_i].firstblocknumber = 0L;
	}
}

/*
 * tuplesort_attach_shared - 附加到共享的 tuplesort 状态
 *
 * 必须由所有工作进程调用。
 */
void tuplesort_attach_shared(Sharedsort *fc_shared, dsm_segment *fc_seg)
{
	/* 附加到 SharedFileSet */
	SharedFileSetAttach(&fc_shared->fileset, fc_seg);
}

/*
 * worker_get_identifier - 分配并返回工作进程的序号标识符
 *
 * 这些标识符分配的顺序没有明确定义，也不应
 * 重要；在并行排序参与者中，工作进程的编号只需
 * 唯一且连续。 logtape.c 需要这样。
 *
 * 请注意，从这里分配的标识符与 
 * ParallelWorkerNumber 没有关系，以避免对
 * 调用者的要求做出任何假设。然而，我们确实遵循 
 * ParallelWorkerNumber 的约定，用 -1 表示非工作进程。 
 * 这包括领导者，以及串行 Tuplesort 进程。
 */
static int fc_worker_get_identifier(Tuplesortstate *fc_state)
{
	Sharedsort *fc_shared = fc_state->shared;
	int			fc_worker;

	Assert(WORKER(fc_state));

	SpinLockAcquire(&fc_shared->mutex);
	fc_worker = fc_shared->currentWorker++;
	SpinLockRelease(&fc_shared->mutex);

	return fc_worker;
}

/*
 * worker_freeze_result_tape - 冻结工作进程的结果磁带供领导者使用
 *
 * 这是在确定结果磁带后立即由工作进程调用的，而不是直接调用 
 * LogicalTapeFreeze()。他们这样做是因为
 * 工作进程需要一些额外的步骤，超出类似的串行 
 * TSS_SORTEDONTAPE 外部排序情况，这里也发生了。这些额外的
 * 步骤围绕释放现在不需要的资源，并向
 * 领导者表示工作进程的输入运行可供其合并。
 *
 * 每个工作进程应该只有一个最终输出运行，这包括
 * 原始输入到工作进程的所有元组。
 */
static void fc_worker_freeze_result_tape(Tuplesortstate *fc_state)
{
	Sharedsort *fc_shared = fc_state->shared;
	TapeShare	fc_output;

	Assert(WORKER(fc_state));
	Assert(fc_state->result_tape != NULL);
	Assert(fc_state->memtupcount == 0);

	/*
	 * 释放大部分剩余内存，以防调用者对我们持有它
	 * 过于敏感。此时， memtuples 可能不是一个微小的合并堆。
	 */
	pfree(fc_state->memtuples);
	/* 保持整洁 */
	fc_state->memtuples = NULL;
	fc_state->memtupsize = 0;

	/*
	 * 并行工作进程需要结果磁带元数据，该数据将存储在
	 * 共享内存中供领导者使用
	 */
	LogicalTapeFreeze(fc_state->result_tape, &fc_output);

	/* 存储输出磁带的属性，并更新已完成的工作进程计数 */
	SpinLockAcquire(&fc_shared->mutex);
	fc_shared->tapes[fc_state->worker] = fc_output;
	fc_shared->workersFinished++;
	SpinLockRelease(&fc_shared->mutex);
}

/*
 * worker_nomergeruns - 在工作进程中转储 memtuples，而不进行合并
 *
 * 这是作为没有合并需求时的 mergeruns() 的替代方案调用的。
 */
static void fc_worker_nomergeruns(Tuplesortstate *fc_state)
{
	Assert(WORKER(fc_state));
	Assert(fc_state->result_tape == NULL);
	Assert(fc_state->nOutputRuns == 1);

	fc_state->result_tape = fc_state->destTape;
	fc_worker_freeze_result_tape(fc_state);
}

/*
 * leader_takeover_tapes - 从工作进程的磁带为领导者创建磁带集
 *
 * 到目前为止，领导者 Tuplesortstate 尚未执行实际的排序。到现在为止，
 * 所有的排序都发生在工作进程中，所有工作进程都必须已经从 
 * tuplesort_performsort() 返回。
 *
 * 当这返回时，领导进程的状态几乎与它作为串行外部排序
 * 生成运行的状态无异。
 */
static void fc_leader_takeover_tapes(Tuplesortstate *fc_state)
{
	Sharedsort *fc_shared = fc_state->shared;
	int			fc_nParticipants = fc_state->nParticipants;
	int			fc_workersFinished;
	int			fc_j;

	Assert(LEADER(fc_state));
	Assert(fc_nParticipants >= 1);

	SpinLockAcquire(&fc_shared->mutex);
	fc_workersFinished = fc_shared->workersFinished;
	SpinLockRelease(&fc_shared->mutex);

	if (fc_nParticipants != fc_workersFinished)
		elog(ERROR, "cannot take over tapes before all workers finish");

	/*
	 * 从工作进程的磁带创建磁带集，包括
	 * 最后一个由领导者拥有的磁带。并行工作进程的成本远高于逻辑磁带，
	 * 因此这里分配的磁带数量永远不应过多。
	 */
	fc_inittapestate(fc_state, fc_nParticipants);
	fc_state->tapeset = LogicalTapeSetCreate(false, &fc_shared->fileset, -1);

	/*
	 * 将currentRun设置为我们将合并的运行次数（它不用于任何目的，这只是形式上的）。
	 */
	fc_state->currentRun = fc_nParticipants;

	/*
	 * 初始化状态，使其看起来与构建初始运行后的状态相同。
	 *
	 * 每个工作节点总是会有恰好1个运行，每个运行恰好有一个输入带，因为工作节点总是输出恰好1个运行，即使对于工作节点没有输入元组进行排序的情况。
	 */
	fc_state->inputTapes = NULL;
	fc_state->nInputTapes = 0;
	fc_state->nInputRuns = 0;

	fc_state->outputTapes = palloc0(fc_nParticipants * sizeof(LogicalTape *));
	fc_state->nOutputTapes = fc_nParticipants;
	fc_state->nOutputRuns = fc_nParticipants;

	for (fc_j = 0; fc_j < fc_nParticipants; fc_j++)
	{
		fc_state->outputTapes[fc_j] = LogicalTapeImport(fc_state->tapeset, fc_j, &fc_shared->tapes[fc_j]);
	}

	fc_state->status = TSS_BUILDRUNS;
}

/*
 * 便利例程，用于释放先前加载到排序内存中的元组
 */
static void fc_free_sort_tuple(Tuplesortstate *fc_state, SortTuple *fc_stup)
{
	if (fc_stup->tuple)
	{
		FREEMEM(fc_state, GetMemoryChunkSpace(fc_stup->tuple));
		pfree(fc_stup->tuple);
		fc_stup->tuple = NULL;
	}
}

int ssup_datum_unsigned_cmp(Datum fc_x, Datum fc_y, SortSupport fc_ssup)
{
	if (fc_x < fc_y)
		return -1;
	else if (fc_x > fc_y)
		return 1;
	else
		return 0;
}

#if SIZEOF_DATUM >= 8
int ssup_datum_signed_cmp(Datum fc_x, Datum fc_y, SortSupport fc_ssup)
{
	int64		fc_xx = DatumGetInt64(fc_x);
	int64		fc_yy = DatumGetInt64(fc_y);

	if (fc_xx < fc_yy)
		return -1;
	else if (fc_xx > fc_yy)
		return 1;
	else
		return 0;
}
#endif

int ssup_datum_int32_cmp(Datum fc_x, Datum fc_y, SortSupport fc_ssup)
{
	int32		fc_xx = DatumGetInt32(fc_x);
	int32		fc_yy = DatumGetInt32(fc_y);

	if (fc_xx < fc_yy)
		return -1;
	else if (fc_xx > fc_yy)
		return 1;
	else
		return 0;
}
